Non-isomorphic graphs with the same numbers of closed walks

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.