Equitable switching and spectra of graphs
type: Item
instance of: scholarly article
title: Equitable switching and spectra of graphs
zbMATH Open document ID: 1015.05058
DOI: 10.1016/S0024-3795(02)00434-2
author: Yasuo Teranishi
published in: Linear Algebra and its Applications
publication date: 2003-03-23T00:00:00Z
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.
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1886832
zbMATH Keywords: graph switching
zbMATH Keywords: equitable partition
zbMATH Keywords: Seidel switching
zbMATH Keywords: Ramanujan graph
reviewed by: Kokichi Sakai
MaRDI profile type: Publication
cites work: Eigenspaces of graphs
cites work: Problems in algebraic combinatorics
cites work: Constructing cospectral graphs
cites work: Chromatic number and the 2-rank of a graph
cites work: Distance-regularity and the spectrum of graphs
cites work: Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
cites work: Q4065581
cites work: Main eigenvalues of a graph
cites work: The second largest eigenvalues of regular bipartite graphs
description: scientific article; zbMATH DE number 1886832