11
$\begingroup$

Can a bipartite graph with at least three vertices have the following properties simultaneously:

  1. Every vertex is the initial vertex of some Hamiltonian path.
  2. The graph contains no Hamiltonian cycle.

I found out that this is only possible if the number of vertices is even and if the partitions have equal size. My conjecture is that there is no bipartite graph with the desired properties, but I cannot prove it.

$\endgroup$
  • $\begingroup$ Bipartite graphs can have a hamiltonian cycle. They just can't have any odd cycles. $\endgroup$ – ChrisD Sep 26 '14 at 23:58
2
$\begingroup$

Yes! The Georges graph has this property. This graph is the smallest known counterexample to the Tutte conjecture that any 3-connected bipartite 3-regular graph is Hamiltonian. It has 50 vertices and 75 edges.

I verified that every vertex is the initial vertex of a Hamiltonian path with some Sage code:

def homtrac_orbits(g):
    orbits = g.automorphism_group(return_group=False, orbits=True)
    return all(g.hamiltonian_path(o[0]) is not None for o in orbits)

def report(G):
    print G.name() + ':', homtrac_orbits(G), G.is_hamiltonian(), G.is_bipartite()

report(Graph(">>graph6<<qO`a`_WO?O?_?_?OO???K?@O?B_?@??__?_I?A?_?_????@?A?@???\
O????g???`????C????????A?????O????C??????????K?????K?????S?????K?????\
B????OO?????__??????C??????C??????A?????C????????D_??????I???????[\
??????AG??????GA_", name="Georges"))

You can see it on SageCell but it takes some time to run. It prints "Georges: True False True" when complete.

The Ellingham-Horton graphs on 54 and 78 vertices are also homogeneously traceable but non-Hamiltonian. The 54-graph can be checked with

report(graphs.EllinghamHorton54Graph())

(included in the above SageCell). I also checked the 78-graph but this is too slow to include in the SageCell.

It seems reasonable to guess that the other known counterexamples to Tutte's conjecture—namely the Owens graph, the Horton 92-graph, and the Horton graph—are also homogeneously traceable, but checking in Sage is too slow for those to verify that way.

$\endgroup$
-2
$\begingroup$

a bipartite graph is acyclic, all vertices of two sets must have at least one connection, graph is two colorable, has distinct edge

$\endgroup$
  • $\begingroup$ a tree or a forest ia acyclic, and every tree or forest is bipartite. Consider the cycle on 4 vertices which is clearly bipartite. Are you sure that your argument is valid? $\endgroup$ – Moritz Oct 22 '15 at 7:45

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.