Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Willie Wong Oct 26 '10 at 16:02
    
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. –  Esha Oct 27 '10 at 4:50
add comment

1 Answer

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.

share|improve this answer
    
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$ –  Esha Oct 28 '10 at 2:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.