Properties of co-spectral graphs (2010)

Originator: Willem Haemers (presented by Sebastian Cioaba - REGS 2011)

Definitions: The adjacency matrix $A$ of a graph $G$ has rows and columns indexed by its vertices (in the same order), with $(u,v)$-entry $1$ when $u$ and $v$ are adjacent and $0$ otherwise. Since $A$ is real and symmetric, its eigenvalues $\lambda_1,\ldots,\lambda_n$ (indexed in nonincreasing order) are real; these are the eigenvalues of $G$, and the multiset of eigenvalues is the spectrum of $G$. Spectral graph theory studies the eigenvalues of graphs and their connections to combinatorial graph parameters. Nonisomorphic graphs with the same spectrum are cospectral, and they are called cospectral mates. A graph $G$ is determined by its spectrum or unispectral if it has no cospectral mates.

Background: In the 1970s, Schwenk proved that almost all trees are NOT unispectral. Recently, Haemers conjectured that almost all graphs are unispectral. In general, proving that a graph is unispectral is nontrivial. Van Dam and Haemers [DH1,DH2] have provided surveys of these topics.

Godsil and McKay [GM] introduced a method of constructing graphs with the same spectrum (called Godsil-McKay switching). Consider a graph $G$ whose vertices can be partitioned into subsets $D, C_1, \dots, C_k$ such that

for $i\ne j$, any two vertices in $C_i$ have the same number of neighbors in $C_j$, and

for each $i$, each vertex in $D$ is adjacent to all, none, or half of $C_i$.

The graph $G'$ obtained by switching in $G$ with respect to the partition $D,C_1,\dots,C_k$ is defined as follows. For each vertex $x\in D$ and each $i$ such that $x$ is adjacent to exactly half of $C_i$, delete these edges and make $x$ adjacent to the other half of $C_i$ instead. All the other edges and vertices remain the same. Godsil and McKay showed that $G$ and $G'$ have the same spectrum, and also their complements have the same spectrum. If $G$ and $G'$ are not isomorphic, then they are cospectral.

Problem 1: Construct (perhaps using Godsil-McKay switching) two cospectral regular graphs $G$ and $G'$ such that $G$ has a perfect matching and $G'$ does not.

Comments: The non-regular graph $C_4+P_k$ is cospectral with the graph obtained from the path $P_k$ by adding two pendant edges at each of its endpoints. When $k$ is even, this graph does not have a perfect matching, but $C_4+P_k$ does.
Aidan Roy used Godsil-McKay switching to construct an example of two connected cospectral graphs $G$ and $G'$ such that $G$ contains a perfect matching and $G'$ does not contain a perfect matching. Stephen Hartke checked by computer all $3$-regular cospectral graphs up to $20$ vertices; they all had the same matching number.

Problem 2: Construct (perhaps using Godsil-McKay switching) two regular cospectral graphs $G$ and $G'$ whose edge-chromatic numbers are different.

References:
[DH1] E. van Dam and W.H. Haemers, Which graphs are determined by their spectrum? (Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002), Linear Algebra Appl. 373 (2003), 241-272.
[DH2] E. van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009), no. 3, 576-586.
[GM] C. Godsil and B. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982), no. 2-3, 257-268.