Note on graphs with irreducible characteristic polynomials
The characteristic polynomial \(P_G\) of a simple graph \(G\) is defined as the characteristic polynomial of its adjacency matrix \(A\): \[ P_G(x) \coloneqq \det(xI-A). \] The irreducibility of \(P_G\) has close relationships with the automorphism group of \(G\), its reconstruction and controllability. For example, \textit{A. Mowshowitz} [in: Proceedings of the 25th summer meeting of the Canadian Mathematical Congress, June 16--18, 1971. Thunder Bay, Ontario, Canada: Lakehead University. 509--522 (1971; Zbl 0323.05117)] showed that if the characteristic polynomial of a graph is irreducible over the integers, then its automorphism group is trivial. \textit{W. T. Tutte} [in: Graph theory and related topics. Proceedings of the conference held in honour of Professor W. T. Tutte on the occasion of his sixtieth birthday, University of Waterloo, July 5--9, 1977. New York - San Francisco - London: Academic Press, A Subsidiary of Harcourt Brace Jovanovich, Publishers. 15--33 (1979; Zbl 0472.05046)] proved that a graph with irreducible characteristic polynomial over \(\mathbb{Q}\) is reconstructible. This article proposes three methods of construction of families of graphs with irreducible characteristic polynomials over \(\mathbb{Q}\): \begin{itemize} \item[1)] by appending paths (Theorems 7, 8 and 9), \item[2)] by union and join (Theorem 10), \item[3)] by corona of \(G\) with \(K_1\) (Theorem 11). \end{itemize} Theorems \(7\) to \(10\) use Eisenstein's criterion (for a polynomial to be irreducible over \(\mathbb{Q}\), see [\textit{V. V. Prasolov}, Polynomials. Translated from the second Russian edition 2001 by Dimitry Leites. Berlin: Springer (2010; Zbl 1272.12001)]). Theorem 11 is based on Sachs' coefficient theorem (see [\textit{D. Cvetković} et al., An introduction to the theory of graph spectra. Cambridge: Cambridge University Press (2010; Zbl 1211.05002)]) and properties of field extensions.
- An introduction to the theory of graph spectra
- Controllable subsets in graphs
- Eigenvalues and automorphisms of a graph
- Further results on controllable graphs
- scientific article; zbMATH DE number 3739586 (Why is no real title available?)
- scientific article; zbMATH DE number 3505005 (Why is no real title available?)
- On a Conjecture of Godsil Concerning Controllable Random Graphs
- On an Irreducibility Theorem of A. Cohn
- Polynomials. Translated from the second Russian edition by Dimitry Leites.
- Prime Numbers and Irreducible Polynomials
- Some results on the spectral reconstruction problem
- Spectral conditions for the reconstructibility of a graph
- The characteristic polynomial of a random matrix
- scientific article; zbMATH DE number 3952816 (Why is no real title available?)
- An upper bound for the height of a tree with a given eigenvalue
- Counterexamples to a conjecture on spectral determination of rooted product with a path
- Constructing cospectral graphs with irreducible characteristic polynomials
- Spectral measures and dominant vertices in graphs of bounded degree
This page was built for publication: Note on graphs with irreducible characteristic polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1979360)
