Does Self Duality imply Hamiltonicity?

103 Views Asked by At

I just looked at some self dual graph examples in the web and found that all of them are hamilton.

Are there non-hamiltonian self dual graphs, or does self duality imply hamiltoncity?

I have no idea, how to tackle this question. Thanks for your help...

EDIT Ok, I found this in Alan Bruce Hill's thesis on Self-Dual Graphs in the "Conclusion and Open Problems" section:

"For example, I conjecture that all 3-connected self-dual graphs are Hamiltonian. One possible approach to that conjecture might be trying to use the radial graphs of Section 2.3. For self-dual planar maps, there is a chance of proving/disproving this using the fact that we know how to construct all such graphs."

Was there any progress since 2002?

1

There are 1 best solutions below

0
On BEST ANSWER

According to this paper by Peter Owens, the following graph is a counterexample:

octohedral_graph_modified

This graph is constructed as follows: start with the octohedral graph and add a vertex for each face. Then join this vertex to the three vertices forming the corresponding face. (This construction is given at the beginning of Section 2 of the aforementioned paper.)