6
$\begingroup$

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).

There are three main classes of criteria for Hamiltonicity that I am aware of:

  1. Dirac-type conditions ($\delta \geq \frac{n}{2}$, i.e. high minimum degree).

  2. Spectral conditions.

  3. Erdos-Chvatal-type conditions ($\kappa \geq \alpha$, i.e. connectivity greater than independence number).

However, none of these approaches is able to settle even the Hamiltonicity of $C_{n}$, the $n$-cycle! Apparently, the reason is that these approaches work best for dense graphs.

Is there an alternative criterion that works well for sparse graphs?

$\endgroup$
2
  • $\begingroup$ Consider the parameterization of (hypercubic) grid graphs: $(x_1,\ldots,x_n)$ specifies a subgraph of the lattice $\mathbb{Z}^n$ which looks like a box with edge lengths $x_i$ and has $P=\prod x_i$-many vertices. Such a graph is Hamiltonian iff $P$ is even. Once one leaves bipartite graphs, such characterizations seem hard to generalize. $\endgroup$ Jan 30, 2014 at 17:12
  • 1
    $\begingroup$ Or more simply: If one starts with a $C_n$ and adds another vertex linked to two of the $C_n$'s vertices, the resulting graph is hamiltonian iff those two vertices are neighbors. Hard to see how a feasible criterion could distinguish here. Worse if linking two additional vertices to the $C_n$ in that way. $\endgroup$
    – Wolfgang
    Jan 30, 2014 at 20:23

1 Answer 1

5
$\begingroup$

Partial answer.

According to Eppstein

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

So in general you can't expect complete answer to your question.

Another reason for Hamiltonicity are forbidden subgraphs, which force Hamiltonicity (possibly with a finite number of exceptions).

Not sure if this works for sparse graphs, perhaps search the web.

Found this: Forbidden subgraphs, hamiltonicity and closure in claw-free graphs

There are theorems of the form:

Every 2-connected $XY$-free graph is hamiltonian.

Where $X,Y$ are explicit small graphs.

For certain type of graphs polynomial time algorithms exist for HC, so if the they work for sparse graphs you can find a cycle, e.g. this paper

$\endgroup$
1
  • $\begingroup$ This looks good! It seems that the 1999 paper you've brought up does work for a cycle! Broadly speaking, I think I might have added a fourth class - criteria for claw-free graphs, which is a kind of sparsity condition, actually. $\endgroup$ Jan 31, 2014 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.