Need some example graphs which are not hamiltonian, i.e, does not admit any hamiltonian cycle, but which have hamiltonian path. It has unique hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|||||||
|
|
2
|
This answer elaborates on Willie Wong's comment and also provides another class of examples. Start with a clique $K_n$, pick two vertices $u, v \in K_n$, and glue two triangles onto $K_n$ at $u$ and $v$. It is easy to see that for any $n$, this graph is not Hamiltonian but there do exist exactly four pairs of vertices that are the endpoints of a Hamiltonian path. Furthermore, instead of using $K_n$, any subgraph such that there exists a Hamiltonian path between the distinguished vertices $u$ and $v$ will still do the trick. Another class of examples is to take the 4-wheel (a 4-cycle with an apex vertex) and to glue one end of a path onto the hub of the wheel. Again, there are mutations of this construction. |
|||
|
