Unimodular equivalence of graphs (Q1194290)

Let \(G\) be a simple graph with \(n\) vertices and \(m\) edges. Denote by \(Q\) the vertex-edge incidence matrix corresponding to some orientation of the edges of \(G\). Define \(L(g)=QQ^ t\) and \(K(G)=Q^ tQ\). Then \(L(G)\) is the so-called Laplacian matrix and \(K(G)\) its edge version. Viewed as integer matrices, the Smith normal form of \(L(G)\) is complicated, but the Smith normal form of \(K(G)\), for connected graphs, is always \(I_{n- 2}\dot+(n)\dot+ 0_{m-n+1}\). An edge version of the matrix-tree theorems is used in the proof. There is an application to digraph flows with constant resultants over abelian groups. Finally, if \(L(G)\) and \(L(H)\) are congruent, then \(G\) and \(H\) have the same chromatic polynomial.