Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  The Masked Avenger Jan 30 at 17:12
1  
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. –  Wolfgang Jan 30 at 20:23

1 Answer 1

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

share|improve this answer
    
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. –  Felix Goldberg Jan 31 at 11:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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