7
$\begingroup$

I am looking for two undirected graphs $G$ and $H$ of the same order (i.e., they have the same number of vertices) such that $G$ and $H$ are

  • cospectral (i.e., their adjacency matrices $A_G$ and $A_H$ have the same multiset of eigenvalues)
  • fractional isomorphic (i.e., there exists a doubly stochastic matrix $S$ such that $A_G\cdot S=S\cdot A_H$, or equivalentlty, $G$ and $H$ have a common equitable partition)

but

  • $G$ and $H$ are not cospectral with regards to their Laplacians (signed or otherwise) or Seidel matrix.

The context for this question can be found in an earlier post Orthogonal similarity of adjacency matrices of graphs which are cospectral and have a common equitable partition.

Improve this question
$\endgroup$
1
  • $\begingroup$ Dear @user64494, if you insist on trying to treat MathOverflow like a book that you are editing, then please get it right. You should either be changing all instances of "cospectral" to "co-spectral", or you should look at the edit you made and get it right. My issue is not with the basic wish to edit, but your mission to do so for trifling reasons, sometimes in ways that are pernickety and incomplete or inconsistent $\endgroup$
    – Yemon Choi
    Jun 22, 2019 at 15:06

1 Answer 1

Reset to default
2
$\begingroup$

EDIT: According to your link, if two graphs are cospectral with a common equitable partition, then they have cospectral complements. But this implies that they have cospectral Seidel matrices (see Theorem 3 in the first reference from your link).

So the best you can do is to not be cospectral with respect to the Laplacian nor signless Laplacian. The two graphs below satisfy this. The equitable partitions are according to the degrees.

Graph6 string: 'H?hRKr?'

Graph6 string:'H?YUPi_'

Verification If $G$ is the top graph and $H$ the bottom graph:

  • Eigenvalues$(G)$=Eigenvalues$(H)\approx\{-2,-2,-1,-1,-0.73205081,1,1,2,2.73205081\}$
  • Their common coarsest equitable partitions are $\{\{2,3,8\},\{0,1,4,5,6,7\}\}$ for $G$ and $\{\{1,3,8\},\{0,2,4,5,6,7\}\}$ for $H$.
  • Eigenvalues$(L_G)\approx\{4.73\times 10^{-16},1, 1.26, 1.26,3, 4, 4, 4.73,4.73\}$ and Eigenvalues$(L_H)\approx \{-2.08\times 10^{-16},0.585,1.26,2,3,3.41,4,4.73, 5\}$

So $G$ and $H$ indeed satisfy the required conditions.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry, did you want them to be not cospectral with respect to all three of the Laplacian, signless Laplacian, and Seidel matrix? Because these are cospectral with respect to their Seidel matrices, but not their Laplacians signless or otherwise. $\endgroup$
    – David Roberson
    Jun 21, 2019 at 22:00
  • $\begingroup$ I was indeed just looking for a pair of graphs that were not cospectral with respect to one of those matrices. Would you care to share how you found these graphs? $\endgroup$
    – Sirolf
    Jun 22, 2019 at 8:57
  • $\begingroup$ Well it is known that two graphs are cospectral if and only if they have the same number of homomorphisms from any cycle, and they are fractionally isomorphic if and only if they admit the same number of homomorphisms from any tree (arxiv.org/abs/1802.08876). So I just constructed two graphs that admit the same number of homomorphisms from any cycle or tree, and then hoped that they would not also be cospectral with respect to their Laplacians. $\endgroup$
    – David Roberson
    Jun 22, 2019 at 10:35
  • $\begingroup$ I see. Well, thanks for the example! $\endgroup$
    – Sirolf
    Jun 22, 2019 at 11:52
  • $\begingroup$ Sorry, I was being a bit snarky. That is sort of how I constructed them, but how I am able to do that is part of ongoing research, so I will keep it to myself for now. Do you need more examples? $\endgroup$
    – David Roberson
    Jun 22, 2019 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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