Equitable switching and spectra of graphs

DOI10.1016/S0024-3795(02)00434-2MaRDI QIDQ1864966zbMATH OpenFDO

Authors Yasuo Teranishi

Publication date 23 March 2003

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(02)00434-2

zbMATH Keywords

equitable partitiongraph switchingRamanujan graphSeidel switching

Mathematics Subject Classification ID

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

Review text

Let \(G\) be a simple graph and \(\pi\) an equitable partition of the vertex set \(V(G)\). It is well known that the characteristic polynomial \(\phi(G/\pi;\lambda)\) of a quotient graph \(G/\pi\) divides that of \(G\). The Seidel switching \(G^\sigma\) of \(G\) with respect to a proper subset \(V\) of \(V(G)\) is called equitable if \(V\) is a union of some cells in \(\pi\). The main result is the following theorem: Let \(\pi\) be an equitable partition of a graph \(G\) and let \(G^\sigma\) be an equitable switching of \(G\) with respect to \(\pi\). Then we have \[ {\phi(G;\lambda)\over \phi(G/\pi; \lambda)}= {\phi(G^\sigma;\lambda)\over \phi(G^\sigma/\pi; \lambda)}. \] Some applications of the above theorem to generalized composition graphs, isospectral graphs, integral graphs and Ramanujan graphs are given. For example the following theorem is obtained: Let \(G\) be a Ramanujan graph with an equitable partition \(\pi\) and let \(G^\sigma\) be an equitable switching of \(G\). If \(G^\sigma\) is connected and regular with \(\deg(G^\sigma)\geq \deg(G)\), then \(G^\sigma\) is a Ramanujan graph if and only if its quotient graph \(G^\sigma/\pi\) is a quotient Ramanujan graph.

Recommendations

• Equitable partition for some Ramanujan graphs
• scientific article; zbMATH DE number 524126
• Godsil-McKay switching and isomorphism
• Note on equitable signed graphs
• On 2-equitable graphs

Cites work

• Chromatic number and the 2-rank of a graph
• Constructing cospectral graphs
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Distance-regularity and the spectrum of graphs
• Eigenspaces of graphs
• scientific article; zbMATH DE number 3482387 (Why is no real title available?)
• Main eigenvalues of a graph
• Problems in algebraic combinatorics
• The second largest eigenvalues of regular bipartite graphs

Cited in

(7)

• Spectral density of equitable core-periphery graphs
• Characteristic polynomials and zeta functions of equitably partitioned graphs
• Invariant subspace, determinant and characteristic polynomials
• Characteristic polynomials of digraphs having a semi-free action
• scientific article; zbMATH DE number 5548726 (Why is no real title available?)
• Equitable partition for some Ramanujan graphs
• Characteristic polynomials of ramified uniform covering digraphs

This page was built for publication: Equitable switching and spectra of graphs

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