The Characteristic Polynomials of Symmetric Graphs
Open Access
Abstract
In this paper, we study the way the symmetries of a given graph are reflected in its characteristic polynomials. Our aim is not only to find obstructions for graph symmetries in terms of its polynomials but also to measure how faithful these algebraic invariants are with respect to symmetry. Let p be an odd prime and be a finite graph whose automorphism group contains an element h of order p. Assume that the finite cyclic group generated by h acts semi-freely on the set of vertices of with fixed set F. We prove that the characteristic polynomial of , with coefficients in the finite field of p elements, is the product of the characteristic polynomial of the induced subgraph by one of . A similar congruence holds for the characteristic polynomial of the Laplacian matrix of .
Keywords
Funding Information
- United Arab Emirates University (G00002762)
This publication has 6 references indexed in Scilit:
- Graph polynomials and symmetriesJournal of Algebra and Its Applications, 2019
- A NOTE ON THE TUTTE POLYNOMIAL AND THE AUTOMORPHISM GROUP OF A GRAPHAsian-European Journal of Mathematics, 2014
- Characteristic polynomials of graph coveringsBulletin of the Australian Mathematical Society, 2004
- Characteristic polynomials of graphs having a semifree actionLinear Algebra and its Applications, 2000
- Characteristic polynomials of symmetric graphsLinear Algebra and its Applications, 1983
- Eigenvalues of Composite MatricesMathematical Proceedings of the Cambridge Philosophical Society, 1961