most recent 30 from http://mathoverflow.net 2013-05-21T04:28:40Z http://mathoverflow.net/feeds/question/43641 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43641/graphs-having-unique-hamiltonian-paths-between-exactly-4-pair-of-vertices Esha 2010-10-26T07:47:33Z 2010-10-28T02:58:13Z

<p>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. </p>

http://mathoverflow.net/questions/43641/graphs-having-unique-hamiltonian-paths-between-exactly-4-pair-of-vertices/43784#43784 Tony Huynh 2010-10-27T10:56:20Z 2010-10-27T15:00:33Z

<p>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. </p> <p>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. </p>