-1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\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$ – Tassle May 2 at 16:42
  • $\begingroup$ I checked the wiki article. The question intends to know about more such classes which have this property. $\endgroup$ – Vk1 May 2 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 Grochow May 3 at 20:06
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. That was quite helpful tip. $\endgroup$ – Vk1 May 3 at 15:07
  • 2
    $\begingroup$ All but one of these classes explicitly includes Hamiltonicity in their definition. $\endgroup$ – Yonatan N May 3 at 19:00

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.