Note on graphs with irreducible characteristic polynomials
type: Item
instance of: scholarly article
title: Note on graphs with irreducible characteristic polynomials
zbMATH Open document ID: 1479.05166
author: Qian Yu
author: Fenjin Liu
author: Hao Zhang
author: Ziling Heng
published in: Linear Algebra and its Applications
publication date: 2021-09-02T00:00:00Z
review text: 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.
reviewed by: Fabien Vignes-Tourneret
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 12F05
zbMATH DE Number: 7390134
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: irreducibility
zbMATH Keywords: Eisentein's criterion
zbMATH Keywords: field extension
zbMATH Keywords: corona
MaRDI profile type: Publication
full work available at URL: j.laa.2021.07.013
OpenAlex ID: W3184741431
cites work: On an Irreducibility Theorem of A. Cohn
cites work: Q3642517
cites work: The characteristic polynomial of a random matrix
cites work: Spectral conditions for the reconstructibility of a graph
cites work: Controllable subsets in graphs
cites work: Q4085747
cites work: Prime Numbers and Irreducible Polynomials
cites work: Polynomials. Translated from the second Russian edition by Dimitry Leites.
cites work: On a Conjecture of Godsil Concerning Controllable Random Graphs
cites work: Further results on controllable graphs
cites work: Eigenvalues and automorphisms of a graph
cites work: Q3926615
cites work: Some results on the spectral reconstruction problem
DOI: 10.1016/J.LAA.2021.07.013
description: scientific article; zbMATH DE number 7390134