Skip to main content
3 of 4
added 127 characters in body
Shahrooz
  • 4.8k
  • 1
  • 24
  • 36

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: a graph $G$ is Highly irregular, if every vertex $v$ of $G$ is adjacent only to vertices with distinct degrees.

I will appreciate any help and guidance.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36