3
$\begingroup$

Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs. What is the smallest 2- or 3-vertex-connected cubic planar bipartite graph with only one (forward and backward counted as one) Hamilton cycle (HC)?

I thought asymmetry might help, but even Frucht's graph, a non-bipartite example, seems to have more than one HC...

$\phantom{}$enter image description here enter image description here enter image description here

And if a single HC is not possible, what is the smallest number and how does the corresponding graph look like?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Have you seen this reference? $\endgroup$ – EuYu Nov 24 '12 at 20:44
  • $\begingroup$ @EuYu Theorem 1 shows that with most of the conditions taken away, it is still impossible. Good work. You might as well put that as an answer since no other answer is possible for this question. $\endgroup$ – Graphth Nov 24 '12 at 20:55
  • $\begingroup$ So, why exactly were you trying to find such graphs? $\endgroup$ – Graphth Nov 24 '12 at 20:55
  • $\begingroup$ @EuYu no I haven't +1 $\endgroup$ – draks ... Nov 24 '12 at 22:05
  • $\begingroup$ @Graphth, just kidding: I'd like to play around with the simplest example containing as few HCs as possible. BTW: Would you mind to share the SAGE script? Did it succeed with an explicite example? $\endgroup$ – draks ... Nov 26 '12 at 14:18
3
+50
$\begingroup$

This paper here seems to suggest that this is impossible. Theorem 1 states that every cubic Hamiltonian graph has at least three Hamiltonian cycles and theorem 10 states that if the graphs are additionally bipartite then they have at least four Hamiltonian cycles.

The article contains quite a few other results which pertain to the subject and it might be of interest to you to peruse through.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Actually, one should attribute this Theorem to Tutte. The above paper only cites Tutte's classic paper On Hamiltonian circuits, where the desired result is obtained as corollary. $\endgroup$ – A.Schulz Nov 26 '12 at 15:26
  • $\begingroup$ Thank you very much, nice reference! $\endgroup$ – draks ... Nov 26 '12 at 23:03
1
$\begingroup$

Based on EuYu, it appears there is no such graph. I originally deleted my answer after that. But, now I put it back so the code is visible. This code will find examples of graphs that satisfy all the conditions EXCEPT the unique Hamilton cycle.

Using Sage, including the nauty generator of graphs, we can generate all graphs with 3 * ord / 2 edges easily. Of course, we only need check graphs with even order as well. So, this should go quick for graphs of small order. But, even at order 12 it might take a very long time. There are over 10 billion graphs of order 12, not sure how many have 18 edges exactly.

# ord must be even
ord = 12
num_edges = 3 * (ord/2)
# This is the string that gets put in the nauty generator to tell it which
# graphs to generate
# E.g., "12 18:18 -c" says generate order 12 graphs with 18 edges that are connected.
nauty_string = str(ord) + " " + str(num_edges) + ":" + str(num_edges) + " -c"
for g in graphs.nauty_geng(nauty_string):

    # check min degree is 3.  Since we have the constraint on edges above
    # this should guarantee the max degree is 3 as well.
    deg = g.degree()
    deg.sort()
    if deg[0] == 3:
        if g.is_bipartite():
            if g.is_planar():
                vert_conn = g.vertex_connectivity()
                if vert_conn >=2:
                    if vert_conn <=3:
                        if g.is_hamiltonian():
                            print g.graph6_string()
print "Finished with", ord
|cite|improve this answer
$\endgroup$
  • $\begingroup$ There is no cubic graph of order 9 at all, if this means number of vertices... $\endgroup$ – draks ... Nov 24 '12 at 20:37
  • $\begingroup$ @draks Yes, I know. I changed the code already to only generate cubic graphs by only looking at graphs with 3 * ord / 2 edges. $\endgroup$ – Graphth Nov 24 '12 at 20:38

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.