Eigenvalues of graphs with twofold symmetry

Publisher Website
Google Scholar
Abstract
There are many cases in which the spectrum of a graph contains the complete spectrum of a smaller graph. The larger (composite) graph and the smaller (component) graph are said to be subspectral. It is shown here that whenever a composite graph G has a twofold symmetry operation which defines two equivalent sets of vertices r and s, it is possible to construct two subspectral components G + and G -, whose eigenvalues, taken jointly, comprise the full spectrum of G. The following rules are given for constructing the components. (1) Draw the r set of vertices and all the edges connecting the members of the set. Then examine in G the vertices through which r and s are connected (the so-called bridging vertices). (2) If a bridging vertex r 1 is connected to its symmetry-equivalent partner s 1, then r 1 is weighted +1 in G + and -1 in G -. (3) If r 1 is connected to a vertex s 2 which is symmetry-equivalent to a second bridging vertex r 2 in r, then the weight of the edge between r 1 and r 2 in G (+1 if they are connected, zero if they are not) is increased by one unit in G + and decreased by one unit in G -. The derivation of these rules is shown, and the relationship between the spectrum of G and the spectra of G + and G - is explained in terms of the symmetry properties of the adjacency matrix of G.