Timeline for Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2013 at 22:33 | comment | added | Mohammad Al-Turkistany | @MichalR.Przybylek I edited the question to restrict the scope and make it answerable | |
| Dec 18, 2013 at 21:59 | comment | added | Michal R. Przybylek | @MohammadAl-Turkistany, I don't think you've asked a research-level question and I doubt it's possible to provide a research-level answer. Here is another great observation --- take the very interesting class of graphs that have at least one vertex of degree 1 and merge it with the very interesting class of graphs consisting of a single cycle. | |
| Dec 18, 2013 at 21:47 | comment | added | Mohammad Al-Turkistany | I'm looking for non-silly classes :). I'm interested in interesting graph classes (similar to the ones in my post) with infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs. The same applies to the Hamiltonian path property. | |
| Dec 18, 2013 at 21:09 | history | answered | David E Speyer | CC BY-SA 3.0 |