are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

Question

Two graphs are isospectral if the combinatorial Laplacian on them has the same spectrum, equivalently, the adjacency matrix has the same the set of eigenvalues (including multiplicities). Two graphs have the same matroid if they are 2-isomorphic, that means there exists a bijection between their edge sets that preserves cycles. There are plenty of examples of isospectral graphs (that are not isomorphic) and it is fairly easy to draw examples of 2-isomorphic graphs but can both of these phenomena occur at the same time?

In general I don't see any reason why no example of this should exist. I know examples of isospectral graphs can be constructed with Seidel switching but this results in graphs with relatively large average degree and usually high connectivity. On the other hand, 3-connected graphs are uniquely determined by their matroid so any potential example cannot be 3-connected.

I am interested in connected non-weighted graphs, I don't care whether they are simple (ie have no loops or multiple edges). Thanks

Answer 1

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automorphism of $X$ that swaps $u$ and $v$. Now form the graph $Y$ from two copies of $X$ by identifying vertex $u$ in the first copy with vertex $u$ in the second, and vertex $v$ in the first with $v$ in the second. Next form $Z$ from two copies of $X$ by identifying $u$'s with $v$'s.

If $u$ and $v$ are adjacent, then then will be a double edge, so we assume that $u$ and $v$ are not adjacent. This means that $Y$ and $Z$ are related by a Whitney flip and hence they have the same cycle matroid.

The graphs $Y$ and $Z$ are cospectral. This follows from Corollary 4.3.2 in my book "Algebraic Combinatorics". Since we only need examples we do not need the proof though, we can just carry out the construction and check.

As example, use Schwenk's tree, constructed as follows. Start with the path on 8 vertices 0,1,...,7 and add a vertex 8 adjacent to 5. Vertices 3 and 6 are cospectral. The graphs we get from the construction are not cospectral. (I just checked using sage.)

For more examples, take any strongly regular graph with trivial automorphism group and take $u$ and $v$ to be two nonadjacent vertices. These examples will be 2-connected.

Answer 2

There exist co-spectral trees. As there are no cycles to preserve, they fit the bill.

As far as 2-connected graphs are concerned, I would try finding a 2-connected graph $\Gamma$ which can be obtained from disjoint graphs $\Gamma_1$ and $\Gamma_2$ by identifying a pair of vertices $u_1,v_1\in V\Gamma_1$ with $u_2,v_2\in V\Gamma_2$, so that the Whitney twist, i.e. identification of $u_1,v_1$ with $v_2,u_2$, gives a non-isomorphic graph, but preserves the characteristic polynomial of the Laplacian matrix of $\Gamma$.