zbMATH — the first resource for mathematics

Determinants of adjacency matrices of graphs. (English) Zbl 1272.05107
Summary: We study the set of all determinants of adjacency matrices of graphs with a given number of vertices. Using Brendan McKay’s data base of small graphs, determinants of graphs with at most 9 vertices are computed so that the number of non-isomorphic graphs with given vertices whose determinants are all equal to a number is exhibited in a table. Using an idea of M. Newman [Can. J. Math. 30, 756–762 (1978; Zbl 0388.15012)], it is proved that if \(G\) is a graph with \(n\) vertices and \({d_1,\dots,d_n}\) is the set of vertex degrees of \(G\), then \(gcd(2m,d^2)\) divides the determinant of the adjacency matrix of \(G\), where \(d=gcd(d_1,\dots,d_n)\). Possible determinants of adjacency matrices of graphs with exactly two cycles are obtained.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A99 Basic linear algebra
15A15 Determinants, permanents, traces, other special matrix functions
Full Text: arXiv