1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Why do you need more examples? How'bout the graph with five vertices formed by joining two triangles at one corner? In fact, start with two triangles join them together by a string of edges, and attach to a vertex along the line a complete graph on some number of vertices, voila, infinitely many examples. $\endgroup$
    – Willie Wong
    Commented Oct 26, 2010 at 16:02
  • $\begingroup$ The first one is not only for triangles, it actually generalizes to a family of graphs and that is exactly the class I have in mind. I would like to see more such "graph families".. preferably construction to generate this kind of graphs. About your next example, I am not very clear. How can you attach a clique at some point on the path between the two triangles? that will form a local loop instead of beoing covered by HP. $\endgroup$
    – Esha
    Commented Oct 27, 2010 at 4:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry, forgot to mention. It has to have unique hamiltonian paths between exactly 4 pair of vertices. Also, tthe triangles can be generalized as $C_m$ for some $m$ $\endgroup$
    – Esha
    Commented Oct 28, 2010 at 2:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .