Timeline for Is there a 2-connected k-regular graph without Hamiltonian path?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 24, 2016 at 20:21 | comment | added | Fedor Petrov | @SebastienPalcoux no, I doubt that it is minimal | |
| Jun 23, 2016 at 11:08 | comment | added | Sebastien Palcoux | Do you expect that $22$ is the smallest order for a $2$-connected $k$-regular non-traceable graph? | |
| Jun 22, 2016 at 23:58 | vote | accept | Sebastien Palcoux | ||
| Jun 22, 2016 at 23:01 | comment | added | Fedor Petrov | I doubt, we need more vertices in paths for making graph $k$-regular. 22 vertices are enough for $k=4$. | |
| Jun 22, 2016 at 22:57 | comment | added | Gerry Myerson | OK. For $k=4$, your construction can give a graph on just 14 vertices. Very good. | |
| Jun 22, 2016 at 22:49 | comment | added | Fedor Petrov | 2) I think, no, because we have $k>3$ paths between $a,b$. Well, for $k=3$ this does not work, but there exist another constructions. | |
| Jun 22, 2016 at 22:47 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
added 1 character in body
|
| Jun 22, 2016 at 22:42 | comment | added | Gerry Myerson | 1) The question is about paths, not cycles. 2) Start at $a$, take one of the paths to $b$, take the other path back to $a$ – isn't that a Hamiltonian cycle? | |
| Jun 22, 2016 at 21:52 | history | answered | Fedor Petrov | CC BY-SA 3.0 |