Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For some pair of non-isomorphic hamiltonian graphs, can there be a chance that it be shown to have the same set of all hamiltonian paths in each graph?

we get the set of all hamiltonian paths in each graph and compare them. If one can get the exact set of another graph by matching each vertex of graph to another - then I call that two graphs have the same set of hamiltonian paths.

By hamiltonian graphs, I mean that graphs have at least one hamiltonian path.

share|improve this question
    
What do you mean by same Hamilton path in two different graphs? –  Brian M. Scott Apr 28 '13 at 10:43
    
we get the set of all hamiltonian paths in each graph and compare them. If one can get the exact set of another graph by matching each vertex of graph to another - then I call that two graphs have the same set of hamiltonian paths. –  HAM Apr 28 '13 at 10:48
    
A cycle graph of length $n$ and a path graph on length $n$ have the same Hamiltonian path $P_n$, and these graphs are not isomorphic. Is this what you are asking? –  Shahab Apr 28 '13 at 10:59
    
@Shahab I edited my question, but anyway: is what you said true? –  HAM Apr 28 '13 at 12:04
add comment

1 Answer

Here’s a trivial counterexample. Neither of these non-isomorphic graphs has a Hamilton path:

           o---o---o                o  
               |                    |  
               o                o---o---o  
               |                    |  
               o                    o

Any bijection between the vertices, however, matches up their (empty) sets of Hamilton paths.

share|improve this answer
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.