Hamiltonicity in graphs of small diameter

45 Views Asked by At

Consider a graph of small diameter, say $O(1)$. Intuitively, it seems that such graphs have a much better chance of being Hamiltonian, since you must be able to "get around" the graph easily. However, I'm unsure how to formalize this; is there any known criteria for such graphs being Hamiltonian?

My main thought has been that Ore's theorem (if $deg(x) + deg(y) \ge n$ for every pair of non-adjacent vertices, then the graph is Hamiltonian) might be helpful, since if some non-adjacent vertices have small degrees, they may force a large diameter, but I'm unconvinced that there are not counterexamples to this idea.

1

There are 1 best solutions below

3
On

If the diameter is $1$ then the graph is complete, so it is hamiltonian for $n\geq 3$.

If the diameter is at least $2$ then we can find a counterexample of arbitrary size by taking the start on $n$ vertices. And if we want the radius to be exactly $k$ we can append a path to one of the leafs of the star.

In general you can consider any graph with at least one vertex of degree $1$.