Two graphs with the same number of walks but without a common equitable partition

Question

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.

Answer 1

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