-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
  • 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$
    – Tassle
    May 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$
    – Vk1
    May 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$ May 3, 2021 at 20:06

1 Answer 1

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, 2021 at 15:07
  • 3
    $\begingroup$ All but one of these classes explicitly includes Hamiltonicity in their definition. $\endgroup$
    – Yonatan N
    May 3, 2021 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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