Note on graphs with irreducible characteristic polynomials (Q1979360)

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.