Constructing cospectral signed graphs

DOI10.1080/03081087.2019.1694483MaRDI QIDQ4959338zbMATH OpenOpenAlexWikidataFDO

Authors Francesco Belardo, Maurizio Brunetti, Matteo Cavaleri, Alfredo Donno

Publication date 13 September 2021

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

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

zbMATH Keywords

adjacency spectrumisospectralPINGswitching

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: A well--known fact in Spectral Graph Theory is the existence of pairs of isospectral nonisomorphic graphs (known as PINGS). The work of A.J. Schwenk (in 1973) and of C. Godsil and B. McKay (in 1982) shed some light on the explanation of the presence of isospectral graphs, and they gave routines to construct PINGS. Here, we consider the Godsil-McKay--type routines developed for graphs, whose adjacency matrices are $(0,1)$-matrices, to the level of signed graphs, whose adjacency matrices allow the presence of $-1$'s. We show that, with suitable adaption, such routines can be successfully ported to signed graphs, and we can build pairs of cospectral switching nonisomorphic signed graphs.

Recommendations

• On cospectral oriented graphs and cospectral signed graphs
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• On a theorem of Godsil and McKay concerning the construction of cospectral graphs
• On cospectral signed digraphs
• scientific article; zbMATH DE number 3885955

Cites work

• A mathematical bibliography of signed and gain graphs and allied areas
• An introduction to the theory of graph spectra
• Compact graphs and equitable partitions
• Constructing cospectral graphs
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
• Enumeration of cospectral graphs.
• Feasibility conditions for the existence of walk-regular graphs
• Graph switching, 2-ranks, and graphical Hadamard matrices
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• Matrices in the theory of signed simple graphs
• Open problems in the spectral theory of signed graphs
• Signed graphs
• Spectra of graphs

Cited in

(18)

• Spectral fundamentals and characterizations of signed directed graphs
• Characterizations of line graphs in signed and gain graphs
• On cospectrality of gain graphs
• Construction of cospectral graphs
• scientific article; zbMATH DE number 3885955 (Why is no real title available?)
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• On cospectral oriented graphs and cospectral signed graphs
• Maximizing the indices of a class of signed complete graphs
• Characterizing signed mixed graphs with small eigenvalues
• A switching method for constructing cospectral gain graphs
• Construction of cospectral graphs, signed graphs and \(\mathbb{T}\)-gain graphs via partial transpose
• On the eigenvalues of complete bipartite signed graphs
• Constructing cospectral graphs via exotic graph products
• Godsil-McKay switchings for gain graphs
• Some results on the complete sigraphs with exactly three non-negative eigenvalues
• A characterization of (K_n,U^-) in the class L(3)
• The NEPS of gain graphs over arbitrary groups and its spectra
• A construction of cospectral signed line graphs

This page was built for publication: Constructing cospectral signed graphs

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