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](https://www.ams.jhu.edu/ers/wp-content/uploads/sites/2/2015/12/fgt.pdf)) 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](https://www.ams.jhu.edu/ers/wp-content/uploads/sites/2/2015/12/fgt.pdf). 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>.



Two graphs with the same number of walks but without a common equitable partition
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](https://doi.org/10.1016/0012-365X(94)90241-0)]).


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](https://doi.org/10.1016/S0195-6698(03)00100-8)]. 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](https://doi.org/10.1016/j.laa.2006.07.017)]). 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](https://doi.org/10.1016/0012-365X(94)90241-0)] 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](https://doi.org/10.1016/S0195-6698(03)00100-8)] 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](https://doi.org/10.1016/j.laa.2006.07.017)] 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>


