Let us denote the edges incident on vertices of valence 2 as "required" as these edges has to be covered by a Hamiltonian circuit, if one exists on that (undirected) graph. Given a graph on which a proper subset of the "required" edges along with two edges incident on a vertex of valency $\geq 3$ form a cycle, can anything related to the Hamiltonicity of the graph be claimed? A few basic rules for the existence of Hamiltonian Cycles is listed here: http://www.mit.edu/~miforbes/ham_cycle.pdf Can rule (4) be extended in any way to answer this query?

  • $\begingroup$ Isn't your question answered in these notes you link to? Rule (4) seems to address you question exactly as it is. If there is a non-Hamiltonian cycle formed by required edges, the graph cannot be Hamiltonian. $\endgroup$ – Karolina Sołtys Nov 8 '10 at 9:39
  • 2
    $\begingroup$ crossposted on MO: mathoverflow.net/questions/45272/… $\endgroup$ – Suresh Venkat Nov 8 '10 at 10:24
  • $\begingroup$ @ Karolina No, it does not. My constraint is " Given a graph on which a PROPER SUBSET of the "required" edges form a cycle" $\endgroup$ – Esha Nov 8 '10 at 10:29
  • 1
    $\begingroup$ @Esha: Regarding crossposting, please see this part of our FAQ. The point is to avoid people on different sites doing double work: meta.cstheory.stackexchange.com/questions/225/… $\endgroup$ – Aaron Sterling Nov 8 '10 at 14:00
  • 1
    $\begingroup$ MO Link: mathoverflow.net/questions/45272/… $\endgroup$ – Esha Nov 9 '10 at 2:24

Asking whether a graph is non-Hamiltonian is CoNP-Complete so it is doubtful that such an algorithm exists.

If you are satisfied with a heuristic that provides a certificates of non-Hamiltonicity, see Bondy and Murty's book (page 53) for a sufficient, but not necessary, condition for non-Hamiltonicity: If $G$ is Hamiltonian then, for every nonempty subset, $S$, of $V$:

$$ \omega(G - S) \le |S| $$

Where $\omega(G - S)$ is the number of connected components left in $G$ after removing the vertices in $S$. A simple counterexample for the converse is the peterson graph: It passes the above test but is not Hamiltonian.

  • $\begingroup$ I don't believe that CoNP-complete is significant here. The reason is that the property cannot be used as a certificate, since it cannot be applied to any graph. It may be possible that Non-Hamiltonicity is in P for this restricted family of inputs. $\endgroup$ – chazisop Jan 10 '11 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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