The characteristic polynomials of symmetric graphs (Q2333884)

Summary: 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 \(\Gamma\) 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 \(\Gamma\) with fixed set \(F\). We prove that the characteristic polynomial of \(\Gamma\), with coefficients in the finite field of \(p\) elements, is the product of the characteristic polynomial of the induced subgraph \(\Gamma [F]\) by one of \(\Gamma \backslash F\). A similar congruence holds for the characteristic polynomial of the Laplacian matrix of \(\Gamma\).