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?
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
|||||||||||||||||
|
|
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. |
|||
|
