DETERMINANTS OF ADJACENCY MATRICES OF GRAPHS

Abstract

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, it is proved that if G is a graph with n vertices, m edges and {d(1,...,)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,...,)d(n)). Possible determinants of adjacency matrices of graphs with exactly two cycles are obtained.