# Non-isomorphic graphs with the same numbers of closed walks

Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:

$1)$ $G_i‎\ncong H_i$ for $i=1, 2, \cdots, n$

$2)$ $|V(G_i)|=|V(H_i)|, |E(G_i)|=|E(H_i)|$

$3)$ If $C_k(G)$ denotes the number of closed walk of length $k$ in graph $G$, we have:

$C_k(G_i)=C_k(H_i)$ for $i=1, 2, \cdots, n$

$4)$ Preferably, I need these graphs be $a)$minimal and $b)$highly irregular(or has one of these two conditions $(a)$ or $(b)$).

$Definition 1:$ A graph $G$ is Highly irregular, if every vertex $v$ of $G$ is adjacent only to vertices with distinct degrees.

$Definition 2:$ The sequence of graphs $G_i$,$i=1,2,\cdots,n$, is minimal, if the number of vertices of every $G_i$ is minimum.

For example, two trees $T_1$ and $T_2$ with degree sequences $4,4,1,1,1,1,1,1$ and $5,2,2,1,1,1,1,1$ respectively, are minimal, because they are minimum vertices co-spectral trees.

I will appreciate any help and guidance.

-
As Igor notes, you have alreadu recieved an answer to this, from MacKay, in response to your question shahrooz.Janbaz (mathoverflow.net/users/19885), Operation on Isospectral graphs, mathoverflow.net/questions/83817 (version: 2011-12-18) –  Chris Godsil Dec 22 '11 at 17:22
Your question is too vague for this forum. Now that you know your condition is same as being cospectral, do a google search for "cospectral graph" and you will find large amounts of information on it. –  Brendan McKay Dec 23 '11 at 0:10
Dear Shahrooz: MathOverflow is not meant to be a substitute for PhD supervision, not for the necessary process of solving one's own problems (or at least finding simpler versions that once can solve) –  Yemon Choi Dec 23 '11 at 12:09
Dear Choi, I know and understand your note. But, I am solving a quite difficult problem that the answer of this question can be very helpful. I don't want some professors solve this problem for me, but I will be so appreciate that they share their experiences with me. Three month ago, I solved a problem about Bandwidth of graph after 6 month effort and thinking, when I introduced the problem here, some of very helpful guidance, showed that this is another version of other problem in design theory. I think here is a place with name Mega-Experience and Idea Sharing. But thank you for your note. –  Shahrooz Dec 23 '11 at 12:22

This is true if and only if the adjacency matrices of your families are (pairwise) isospectral. Since you already know how to construct regular isospectral graphs, you know how to answer your question.

-

There is a nice paper about this kind of question: Waiting for a bat to fly by (in polynomial time), by Itai Benjamini, Gady Kozma, Laszlo Lovasz, Dan Romik and Gabor Tardos (arXiv:math/0310435).

They address exactly this question, phrased a bit differently: launch a simple random walk in a finite graph, and observe only its successive return times to a marked vertex; what can you tell about the shape of the graph from this information? They exhibit an example of two graphs with the same return time distribution, and from there by adding pieces you should be able to produce examples of all sizes.

As you notice, there are things like the number of vertices that are easy to compute, and there are graphs that are indistinguishable that way; the main question in the paper is, replacing the SRW by something else that is observed only at a given vertex (say some Glauber dynamics), can you do better than a single SRW?

(Plus, I like the title of the paper very much ;->)

-
Dear Meyerowitz, We say a graph $G$ is Highly irregular, if every vertex $v$ of $G$ is adjacent only to vertices with distinct degrees. I know that we can find a lot of co-spectral graphs in tree that they have very different degree. But, the condition minimal and highly irregularity is very important. But, I will add the definition of highly irregularity to the question. thank you –  Shahrooz Dec 23 '11 at 11:56