Determinants of adjacency matrices of graphs

Document Type : Research Paper

Author

University of Isfahan

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,\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‎.

Keywords

Main Subjects


S. Akbari, E. Ghorbani, H. Kharaghani, and G. B. Khosrovshahi Graphs with extremal determinants. preprint. K. P. Costello and V. H. Vu (2008). The rank of random graphs. Random Structures Algorithms. 33, 269-285 D. M. Cvetkovi\'c, M. Doob and H. Sachs (1980). Theory and Application, Pure and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London. 87 S. Fallat and P. van den Driessche (1997). Maximum determinant of $(0,1)$ matrices with certain constant row and column sums. Linear and Multilinear Algebra. 42 (4), 303-318 W. H. Haemers and Q. Xiang (2010). Strongly regular graphs with parameters $(4m^4, 2m^4 + m^2,m^4 + m^2,m^4 + m^2)$ exist for all $m > 1$. European J. Combin.. 31 (6), 1553-1559 J. Hadamard (1968). R\'esolution d'une question relative aux determinants. Selecta, pp. 136-142, Gauthier-Villars, Paris, 1935 and Oeuvres, Tome I, CNRS, Paris. , 239-245 S. Hu (2003). The Classification and maximum determinants of the adjacency matrices of graphs with one cycle. J. Math. Study. 36 (1), 102-104 M. Newman (1978). Combinatorial matrices with small determinants. Canad. J. Math.. 30, 756-762 H. J. Ryser (1956). Maximal determinants in combinatorial investigations. Canad. J. Math.. 8, 245-249
Volume 1, Issue 4 - Serial Number 4
December 2012
Pages 9-16
  • Receive Date: 16 June 2012
  • Revise Date: 24 November 2012
  • Accept Date: 28 November 2012
  • Published Online: 01 December 2012