One trivial class of graphs is the class consisting of complete graphs or complete bipartite graphs with equal sized partitions. I would love to know if more such classes exist.
3
-
3$\begingroup$ The wikipedia article for Hamiltonian path gives some sufficient conditions (mainly the Bondy–Chvátal theorem and special cases as well as the fact that any 4-connected planar graph has a Hamiltonian path). $\endgroup$– TassleMay 2, 2021 at 16:42
-
$\begingroup$ I checked the wiki article. The question intends to know about more such classes which have this property. $\endgroup$– Vk1May 2, 2021 at 17:25
-
$\begingroup$ It's a (fairly) well-known open question as to whether every Cayley graph is Hamiltonian. Pak & Radoicic 2008 $\endgroup$– Joshua GrochowMay 3, 2021 at 20:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
A good resource to answer questions like this is graphclasses.org. You find the graph class you care about -- in this case, Hamiltonian graphs. Then check the maximal subclasses section, and possibly forward-search from there.
-
-
3$\begingroup$ All but one of these classes explicitly includes Hamiltonicity in their definition. $\endgroup$ May 3, 2021 at 19:00