Generalized spectral characterizations of almost controllable graphs

DOI10.1016/J.EJC.2021.103348zbMATH Open1466.05124arXiv2010.15888OpenAlexW3158548957MaRDI QIDQ2033889FDOQ2033889

Authors: Wei Wang, Fenjin Liu, Wei Wang 

Publication date: 18 June 2021

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

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.

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

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_\alpha\)-spectral characterizations of almost \(\alpha\)-controllable graphs
• Further results on controllable graphs
• Controllable graphs with least eigenvalue at least \(-2\)

zbMATH Keywords

cospectral graphsspectra of graphsBinet-Cauchy formula

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A note on cospectral graphs
• Some results on graph spectra
• Controllable subsets in graphs
• A sufficient condition for a family of graphs being determined by their generalized spectra
• The main eigenvalues of a graph: a survey
• 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 simple arithmetic criterion for graphs being determined by their generalized spectra
• Generalized spectral characterization of graphs revisited
• A note on non-\(\mathbb{R}\)-cospectral graphs

Cited In (14)

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

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)