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$
$\endgroup$
9
-
$\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łtysNov 8, 2010 at 9:39
-
2$\begingroup$ crossposted on MO: mathoverflow.net/questions/45272/… $\endgroup$– Suresh VenkatNov 8, 2010 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$– EshaNov 8, 2010 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 SterlingNov 8, 2010 at 14:00
-
1$\begingroup$ MO Link: mathoverflow.net/questions/45272/… $\endgroup$– EshaNov 9, 2010 at 2:24
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
1
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$– chazisopJan 10, 2011 at 9:22