# 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 ;->)

-

Look around. The term cospectral is also used. Some of the people who have been answering you showed that Almost all Trees are Co-spectral. Of course trees can be quite irregular. An early paper is Cospectral Graphs and Digraphs Bull. London Math. Soc. (1971) 3(3): 321-328 Frank Harary, Clarence King, Abbe Mowshowitz, and Ronald C. Read. It has some nice pictures. It might be that almost all graphs share their spectrum with another non-isomorphic graph (in some precise sense). It might also be the case that almost all graphs are determined up to automorphism by their spectra (in some precise sense of almost all.) But once you have some cospectral graphs you can make lots more by combining them in various ways. It might not be that satisfying to explicitly describe examples (by a picture or adjacency matrix.).The thing about the latin square graphs is that with very little work one can describe how to get thousands of mutually non-isomorphic graphs all with the same spectrum.

-
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
Unfortunately, many of trees are not highly irregular. The definition of "Highly Irregular Graphs" is from a paper with this name that " Yousef Alavi, Gary Chartrand, F.R.K Chung, Paul Erdos, R.L. Graham and Ortrud R. Oellermann" published it in Journal of Graph Theory, Vol 11,No 2, 235-249(1987). –  Shahrooz Dec 23 '11 at 12:06
I think that nobody here (including me) remembered that "highly irregular" is a defined property. It isn't very common. Please add a definition of "minimal" too, since it can mean many things. –  Brendan McKay Dec 23 '11 at 12:48
Sorry, you are right. I will edit the question and add the definition of minimal word. Thank you –  Shahrooz Dec 23 '11 at 15:15