Generalized spectral characterizations of almost controllable graphs

DOI10.1016/J.EJC.2021.103348MaRDI QIDQ2033889zbMATH OpenOpenAlexFDO

Authors Wei Wang, Fenjin Liu, Wei Wang

Publication date 18 June 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.15888

zbMATH Keywords

cospectral graphsspectra of graphsBinet-Cauchy formula

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Controllability (93B05)

Abstract: Characterizing graphs by their spectra is an important topic in spectral graph theory, which has attracted a lot of attention of researchers in recent years. It is generally very hard and challenging to show a given graph to be determined by its spectrum. In Wang~[J. Combin. Theory, Ser. B, 122 (2017):438-451], the author gave a simple arithmetic condition for a family of graphs being determined by their generalized spectra. However, the method applies only to a family of the so called emph{controllable graphs}; it fails when the graphs are non-controllable. In this paper, we introduce a class of non-controllable graphs, called emph{almost controllable graphs}, and prove that, for any pair of almost controllable graphs $G$ and $H$ that are generalized cospectral, there exist exactly two rational orthogonal matrices $Q$ with constant row sums such that $Q^{mT}A(G)Q=A(H)$, where $A(G)$ and $A(H)$ are the adjacency matrices of $G$ and $H$, respectively. The main ingredient of the proof is a use of the Binet-Cauchy formula. As an application, we obtain a simple criterion for an almost controllable graph $G$ to be determined by its generalized spectrum, which in some sense extends the corresponding result for controllable graphs.

Recommendations

• A new criterion for almost controllable graphs being determined by their generalized spectra
• The overgraphs of generalized cospectral controllable graphs
• On the generalized A_-spectral characterizations of almost -controllable graphs
• Further results on controllable graphs
• Controllable graphs with least eigenvalue at least \(-2\)

Cites work

• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• A new arithmetic criterion for graphs being determined by their generalized \(Q\)-spectrum
• A new method for constructing graphs determined by their generalized spectrum
• A note on cospectral graphs
• A note on non-\(\mathbb{R}\)-cospectral graphs
• A simple arithmetic criterion for graphs being determined by their generalized spectra
• A sufficient condition for a family of graphs being determined by their generalized spectra
• Controllable subsets in graphs
• Generalized spectral characterization of graphs revisited
• Some results on graph spectra
• The main eigenvalues of a graph: a survey

Cited in

(14)

• The Smith normal form of the walk matrix of the Dynkin graph \(D_n\) for \(n \equiv 0 \pmod{4}\)
• Generalized spectral characterizations of a new family of noncontrollable graphs
• On the generalized \(A_\alpha\)-spectral characterizations of almost \(\alpha\)-controllable graphs
• Construction of graphs with distinct \(A_\alpha \)-eigenvalues
• Generalized distance spectral characterizations of graphs based on Smith norm form
• Laplacian controllability for graphs with integral Laplacian spectrum
• An improved condition for a graph to be determined by its generalized spectrum
• Signed graphs with exactly two distinct main eigenvalues
• Almost controllable graphs and beyond
• The overgraphs of generalized cospectral controllable graphs
• Smith normal form and the generalized spectral characterization of oriented graphs
• On the walk matrix of the Dynkin graph \(D_n\)
• Further results on almost controllable graphs
• A new criterion for almost controllable graphs being determined by their generalized spectra

This page was built for publication: Generalized spectral characterizations of almost controllable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033889)