0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by same Hamilton path in two different graphs? $\endgroup$ – Brian M. Scott Apr 28 '13 at 10:43
  • $\begingroup$ 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. $\endgroup$ – HAM Apr 28 '13 at 10:48
  • $\begingroup$ 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? $\endgroup$ – Shahab Apr 28 '13 at 10:59
  • $\begingroup$ @Shahab I edited my question, but anyway: is what you said true? $\endgroup$ – HAM Apr 28 '13 at 12:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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