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?

$\endgroup$
9
  • 1
    $\begingroup$ Have you seen this reference? $\endgroup$
    – EuYu
    Nov 24, 2012 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$
    – GeoffDS
    Nov 24, 2012 at 20:55
  • $\begingroup$ So, why exactly were you trying to find such graphs? $\endgroup$
    – GeoffDS
    Nov 24, 2012 at 20:55
  • $\begingroup$ @EuYu no I haven't +1 $\endgroup$
    – draks ...
    Nov 24, 2012 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, 2012 at 14:18

2 Answers 2

Reset to default
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.

$\endgroup$
2
  • 2
    $\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, 2012 at 15:26
  • $\begingroup$ Thank you very much, nice reference! $\endgroup$
    – draks ...
    Nov 26, 2012 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
$\endgroup$
2
  • $\begingroup$ There is no cubic graph of order 9 at all, if this means number of vertices... $\endgroup$
    – draks ...
    Nov 24, 2012 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$
    – GeoffDS
    Nov 24, 2012 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .