Grinberg-Introduction-Graph-Theory · Problem 5.20

Trees and arborescences

Mathematics — Graph Theory · laplacian-positive-semidefinite

Problem

Let G=(V,E,φ)G = (V, E, \varphi) be a multigraph. Let LL be the Laplacian of the digraph GbidirG^{\mathrm{bidir}}. Prove that LL is positive semidefinite. [Hint: Write LL as NTNN^T N, where NN or NTN^T is some matrix you have seen before. Note that the statement is not true if we replace GbidirG^{\mathrm{bidir}} by an arbitrary digraph DD.]

Browse the problem library