4
$\begingroup$

Let $G$ and $H$ be two undirected graphs of the same order (i.e., they have the same number of vertices). Denote by $A_G$ and $A_H$ the corresponding adjacency matrices. Furthermore, denote by $\bar G$ and $\bar H$ the complement graphs of $G$ and $H$, respectively.

When $G$ and $H$ are cospectral, and $\bar G$ and $\bar H$ are cospectral, it is known (see e.g., Theorem 3 in Van Dam et al. [1]) that there exists an orthogonal matrix $O$ such that $A_G\cdot O=O\cdot A_H$ and furthermore, $O\cdot \mathbf{1}=\mathbf{1}$, where $\mathbf{1}$ denotes the vector consisting of all ones.

Suppose that, in addition, $G$ and $H$ have a common equitable partition. That is, there exist partitions ${\cal V}=\{V_1,\ldots,V_\ell\}$ of the vertices in $G$ and ${\cal W}=\{W_1,\ldots,W_\ell\}$ of the vertices in $H$ such that (i) $|V_i|=|W_i|$ for all $i=1,\ldots,\ell$; and (ii) $\text{deg}(v,V_j)=\text{deg}(w,W_j)$ for any $v$ in $V_i$ and $w$ in $W_i$, and this for all $i,j=1,\ldots,\ell$.

Question:

  • What extra structural conditions on the orthogonal matrix $O$, apart from $A_G\cdot O=O\cdot A_H$ and $O\cdot \mathbf{1}=\mathbf{1}$, can be derived when $G$ and $H$ are cospectral, have cospectral complements, and have a common equitable partition?

I am particularly interested in showing that one can assume that $O$ is block structured according to the partitions involved. That is, if $\mathbf{1}_{V_i}$ and $\mathbf{1}_{W_i}$ denote the indicator vectors of the (common) partitions ${\cal V}$ and ${\cal W}$, respectively, can $O$ be assumed to satisfy $$ \text{diag}(\mathbf{1}_{V_i})\cdot O=O\cdot \text{diag}(\mathbf{1}_{W_i}), $$ for $i=1,\ldots,\ell$? Here, $\text{diag}(v)$ for a vector $v$ denotes the diagonal matrix with $v$ on its diagonal.


UPDATE

Since my posting, the following came to my attention:

  • Cospectral graphs with a common equitable partition necessarily have cospectral complements. So, the latter assumption can be removed. Indeed, graphs with a common equitable partition are easily seen to have the same number of walks of any length. When, in addition the graphs are cospectral, Theorem 3 in [1] and Theorem 1.3.5 in [2] imply that they must have cospectral complements.
  • Graphs $G$ and $H$ for which there exists an orthogonal matrix $O$ such that (i) $A_GO=OA_H$; (ii) $O\mathbf{1}=\mathbf{1}$; and (iii) $\mathsf{diag}(\mathbf{1}_{V_i})O=O\mathsf{diag}(\mathbf{1}_{W_i})$ for $i=1,\ldots,\ell$, where characterised [3] as graphs that are cospectral wrt to the WL$_1$-closure of the adjacency matrices. Here, the $\mathsf{WL}_1$-closure can be considered to be an extension of the generalized adjacency matrix. It can be inductively defined by means of symbolic expressions $e$, as follows.
    • basic expressions $e=X$, $e=I$, $e=J$ with $X$ a matrix variable, $I$ identity matrix, $J$ the all-ones matrix (all of the same dimension) are in $\mathsf{WL}_1(X)$;
    • if $e_1$ and $e_2$ are expressions in $\mathsf{WL}_1(X)$, then also $e_1+e_2$, $e_1\cdot e_2$, $e_1^*$, and $a\cdot e_1$ for scalars $a\in\mathbb{C}$, are in $\mathsf{WL}_1(X)$;
    • if $e$ is an expression in $\mathsf{WL}_1(X)$, then also $\mathsf{diag}(e(X)\mathbf{1})$ is in $\mathsf{WL}_1(X)$.

Then $G$ and $H$ are cospectral wrt $\mathsf{WL}_1(A_G)$ and $\mathsf{WL}_1(A_H)$ when $e(A_G)$ and $e(A_H)$ are cospectral for any expression $e$ in $\mathsf{WL}_1(X)$. (In particular, they will be cospectral wrt their adjacency matrices, adjacency matrices of their complements, Seidel matrix, Laplacian, normalized Laplacian, ...)

It is shown (Lemma 9 in [3]) that when $G$ and $H$ are cospectral wrt $\mathsf{WL}_1(A_G)$ and $\mathsf{WL}_1(A_H)$ then $G$ and $H$ are cospectral (trivial) and $G$ and $H$ have a common equitable partition.

Revised question My original question thus asked whether the converse also holds. That is, are any two cospectral graphs with a common equitable partition necessarily cospectral wrt to the WL$_1$-closure of the adjacency matrices? If not, what is a counter example?

As a final remark, Theorem 6.2 in [4] seems to imply that cospectrality and having a common equitable partition is equivalent to the existence of an orthogonal matrix $O$ such that $A_GO=OA_H$, $O=S+T$ for a doubly stochastic matrix $S$, $A_GS=SA_H$, and such that for $i=1,\ldots,\ell$,

  • $\mathbf{1}_{V_i}=S\mathbf{1}_{W_i}$, $\mathbf{1}^t_{V_i}S=\mathbf{1}^t_{W_i}$
  • $\mathbf{0}=T\mathbf{1}_{W_i}$, $\mathbf{0}=\mathbf{1}^t_{V_i}T$.

Hence, the orthogonal matrix $O$ can be assumed to satisfy $\mathbf{1}_{V_i}=O\mathbf{1}_{W_i}$ for $i=1,\ldots,\ell$. This is a weaker condition than $\mathsf{diag}(\mathbf{1}_{V_i})O=O\mathsf{diag}(\mathbf{1}_{W_i})$.

[1] Cospectral graphs and the generalized adjacency matrix, E.R. van Dam, W.H. Haemers, J.H. Koolen. Linear Algebra and its Applications 423 (2007) 33–41. https://doi.org/10.1016/j.laa.2006.07.017

[2] Dragoš M. Cvetković, Peter Rowlinson, and Slobodan Simić. An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts. Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511801518.

[3] Mario Thüne. Eigenvalues of matrices and graphs. PhD thesis, University of Leipzig, 2012. http://ul.qucosa.de/api/qucosa%3A12068/attachment/ATT-0/

[4] Ada Chan and Chris D. Godsil. Symmetry and eigenvectors. In Graph symmetry (Montreal, PQ, 1996), volume 497 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 75–106. Kluwer Acad. Publ., Dordrecht, 1997. https://doi.org/10.1007/978- 94- 015- 8937- 6_3.

$\endgroup$
  • 1
    $\begingroup$ Perhaps a good starting point could be to find two graphs of the same order that are co-spectral and have a common equitable partition, yet are not cospectral with regards to their (signed) Laplacians or Seidel matrix? This would suffice to distinguish the two settings mentioned above. $\endgroup$ – Sirolf Jun 19 at 15:00
  • $\begingroup$ I posted the previous comment as a new question. See link $\endgroup$ – Sirolf Jun 21 at 12:38

Your Answer

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

Browse other questions tagged or ask your own question.