Consider two undirected graphs $G$ and $H$ of the same order (same number of vertices).

If $G$ and $H$ have a common equitable partition, then it is known (see e.g., Chapter 6 in 1) that these graphs must have the same number of walks of any length. (after all, they have the same iterated degree sequence.)

I am interested in finding two graphs of the same order which

  • have the same number of walks of any length (i.e., they have the same main eigenvalues and main angles);
  • yet do not have a common equitable partition; and
  • have a different number closed walks of a certain length (i.e. they are not cospectral).

Any such an example would be appreciated.

1. Edward R. Scheinerman and Daniel H. Ullman. Fractional Graph Theory: a Rational Approach to the Theory of Graphs. John Wiley & Sons, 1997. https://www.ams.jhu.edu/ers/wp-content/uploads/sites/2/2015/12/fgt.pdf.


It appears that one way to obtain a desired example pair $G$ and $H$ is to let $G$ be the disjoint union $G_1\cup G_2$ and $H$ be the disjoint union of $H_1\cup H_2$, such that

  • $G_1$ and $H_1$ have a common equitable partition, yet are not co-spectral; and
  • $G_2$ and $H_2$ have the same number of walks of any length, yet they have no common equitable partition.

Clearly, the resulting graphs $G$ and $H$ will not be co-spectral and similarly won't have a common equitable partition. Nevertheless, the property of that $G_1$ and $H_1$, and $G_2$ and $H_2$, have the same number of walks of any length is preserved by the union.

To be more explicit:

For $G_1$ and $H_1$ one can take, e.g., $C_6$ (cycle of length $6$) and $2C_3$ (two disjoint triangles). These graphs are known not to be co-spectral and have a common equitable partition (see e.g., Fig. 3 in [1]).

For $G_2$ and $H_2$ one can just take the pair of co-spectral graphs with co-spectral complements given in Fig. 4 in [2]. That is, $G_2$ is $C_6\cup K_1$ (cycle of length $6$ with an additional isolated vertex) and $H_2$ is a star with one central vertex from which $3$ paths of length 2 start. Co-spectral graphs with co-spectral complements are known to have the same number of walks of any length (see Theorem 3 in [3]). Furthermore, since $G_2$ has an isolated vertex whereas $H_2$ does not, they cannot have a common equitable partition (as their degree sequences must coincide.)

This results in graphs $G$ and $H$ consisting of 13 vertices. Perhaps smaller examples can be found.

[1] Fractional isomorphism of graphs, M. V.Ramanaa, E. R.Scheinerman and D. Ullman, Vol. 132, Issues 1–3, pp. 247-26, 1994. https://doi.org/10.1016/0012-365X(94)90241-0

[2] Enumeration of cospectral graphs, W. H. Haemers and E. Spence, European Journal of Combinatorics, Vol. 5, Issue 2, pp. 199-211, 2004. https://doi.org/10.1016/S0195-6698(03)00100-8

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


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.