Hamiltonian graphs with high degree and high girth

graph theoryhamiltonian-path

Given integers $d\ge2$ and $k\ge3$, is there a Hamiltonian (simple) graph $G$ with minimum degree $\delta(G)=d$ and girth $g(G)\ge k$? And if so, what is the minimum number of vertices, call it $N(d,k)$, for such a graph?

I know the answer in a few trivial cases.

$d=2$: Yes, $N(2,k)=k$, attained by the cycle graph $C_k$.

$k=3$: Yes, $N(d,3)=d+1$, attained by the complete graph $K_{d+1}$.

$k=4$: Yes, $N(d,4)=2d$, attained by the complete bipartite graph $K_{d,d}$.

$d=3,k=5$: Yes, $N(3,5)=12$, attained by the following cubic graph of order $12$ which probably has a name but I don't know what it is. It has nine vertices $v_0,v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8$ which are joined cyclically, and three more vertices $w_0,w_1,w_2$ with $v_i$ joined to $w_j$ iff $i\equiv j\pmod3$. One Hamiltonian cycle is $v_0,v_1,w_1,v_4,v_5,v_6,v_7,v_8,w_2,v_2,v_3,w_0,v_0$.

Best Answer

Here are a few more specific values:

All of these are $(d,k)$-cages, and in general a $(d,k)$-cage is a good candidate for being a minimal example, but there is no guarantee. First of all, it is a matter of chance that all three of the above graphs are Hamiltonian; other examples like the Petersen graph (a $(3,5)$-cage) are not. Second, cage graphs are all regular, which is not a requirement here.

However, if a cage graph is reasonably close to the Moore bound, we can prove that any example which is not regular would have more vertices. For example, consider the Robertson graph. If there is an example with $d=4$ and $k=5$ which is not regular, it would have to have a vertex of degree $5$. Its five neighbors each have $3$ more neighbors, which are all distinct because otherwise a $4$-cycle would be formed. This is already $21>19$ vertices.

Random regular graphs give us a proof that $N(d,k)$ exists for all $k$, but without particularly good guarantees on what it is.

A random $d$-regular graph on $n$ vertices:

  1. Is Hamiltonian w.h.p. as $n \to \infty$, provided $d \ge 3$ (Robinson and Wormald, Almost all regular graphs are hamiltonian).
  2. Has girth at least $k$ with probability tending to $\exp\left(-\sum_{j=3}^{k-1} \frac{(d-1)^j}{2j}\right)$ as $n \to \infty$ (Wormald, The asymptotic distribution of short cycles in random regular graphs).

So if $n$ is sufficiently large, then with positive probability a random $d$-regular graph will have the properties we want.

The Ramanujan graphs constructed by Lubotzky, Phillips and Sarnak give an explicit construction that will work here. Probably. For primes $p,q$ congruent to $1$ mod $4$ this is a $(p+1)$-regular graph with:

  • $q(q^2-1)$ vertices and girth at least $4 \log_p q - \log_p 4$, if $\left(\frac qp\right)=-1$;
  • $\frac12 q(q^2-1)$ vertices and girth at least $2\log_p q$, if $\left(\frac qp\right)=1$.

Are they Hamiltonian? Well, they are Cayley graphs, and there's a conjecture that's still open as far as I know that all Cayley graphs are Hamiltonian. So they probably are; but I don't know of an actual proof for this construction. The only Hamiltonian thing mentioned in Lubotzky, Phillips and Sarnak's paper is quaternions.

Related Question