Equitable switching and spectra of graphs (Q1864966): Difference between revisions

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.