1
$\begingroup$

I am looking for a large family (infinite pairs) of cospectral graphs with these condtions:

  • The graphs are non-regular,

  • Minimum degree is greater than $1$,

  • The degree sequences of these cospectral graphs are the same.

I need cospectrality by adjacency matrix and the graphs are simple.

The motivation for asking this question is that; if we have counterexample for reconstruction conjecture, the two graphs have these properties. I want to study such family of graphs.

$\endgroup$
1
$\begingroup$

Let $D$ be a Steiner triple system on $v$ points. (So $v\equiv1,3$ mod 6). The incidence graph is the bipartite graph with the $v$ points as one colour class and the $v(v-1)/6$ blocks as the second; a point is incident with the $(v-1)/2$ blocks that contain it.

Let $N$ be the point-block incidence matrix of the system. Then $NN^T=\frac12(v-3)I+J$ and $NN^T$ has the same non-zero eigenvalues as $NN^T$, with the same multiplicities. The adjacency matrix $A$ has the form $$A =\begin{pmatrix}0&N\\ N&0\end{pmatrix}$$ and $$A^2 =\begin{pmatrix}NN^T&0\\ 0&N^TN\end{pmatrix}$$ from which it follows that spectrum of $A$ is determined by $v$.

The incidence graphs have degree set $\{3,(v-1)/2\}$, so these graphs are not regular if $v\ge9$. There are 80 Steiner triple systems on 15 points and Kaski and Ostergard showed that there are 11,084,874,829 on 19 points.

The number of walks of length $k$ in an incidence graph is determined by $v$ (exercise) and it follows that the complements of the incidence graphs are also cospectral.

$\endgroup$
2
  • $\begingroup$ Dear Godsil, thanks for your good answer. Do you know other family of such graphs that has more diversity on degree sequences? $\endgroup$ – Shah Rooz Mar 21 at 20:31
  • 1
    $\begingroup$ @Shah Rooz: for a start, Cartesian products of the above. $\endgroup$ – Chris Godsil Mar 21 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.