Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my perspective, it doesn't seem too impressive, the argument is rather elementary, but I can't find another paper which states what I found. The closest I could find was Jan Florek's On Barnette's Conjecture, which is about a subcase which I was previously aware of.

Definitions: It is well-known that a cubic polyhedral graph, $P$, is Hamiltonian iff its dual, $D$, can be partitioned into two sets of vertices, $A,B$, such that the induced subgraphs $D[A]$ and $D[B]$ are both trees. A dual with this condition is said to have a tree-partitioning.

Since a dual, $D$, of cubic bipartite polyhedral graph is triangularized, and has a unique 3-coloring, I found it easier to think about removing all vertices in one color class, which gives us a 2-connected bipartite graph, $S$, with a fixed planar embedding. To recover $D$ from $S$, for each face, $f$ in $S$, we add a vertex $v_f$, and add edges between $v_f$ and all vertices $u$ incident to $f$. This recovery process is well defined, and shall be denoted as $D(S)$.

My result says: if a bipartite 2-connected planar embedded graph, $S$, is constructible (in a way defined below), then $D(S)$ has a tree partitioning, and thus is the dual of a Hamiltonian bipartite cubic polyhedral graph.

Construction Method:

Throughout, the "exterior cycle" of a connected component is the cycle that creates a polygon with the largest area with respect to how the component is embedded.

  1. We start with $S_1$ being an even cycle graph $C_{2k_0}$, with a planar embedding. Currently, all vertices of $S_1$ make up its "exterior cycle".
  2. If the exterior cycle has four vertices, we may choose to stop at $S_i$, or may continue
  3. Embed a new even cycle graph $C_{2k_i}$ as a new component, such that all vertices are outside the exterior cycle of $S_i$
  4. Choose two paths of length $2 \leq l \leq 4 $ along the exterior cycles of your two components, $p_1 = v_1,v_2 \dots v_l, p_2 = u_1,u_2,\dots u_l$.
  5. Add edges $(v_j,u_j)$ for all $1 \leq j \leq l$, and contract said edges. (moving the location of $u_j$ to $v_j$ in the embedding)
  6. Return to step 2.

Any $S_i$ at which we can stop at step 2, is constructible. My result above is gotten from a rather simple inductive argument. The class of graphs which are made Hamiltonian contains those proven by Florek, in fact, this is specifically the case when $k_i = 2$ for $i > 0$, and one may use a even shorter argument for this case.

Is this result known, and if not, does the fact that the family of graphs is rather difficult to describe detract from its value?

Edit: I just realized that there is an second result of my methods. If $P$ is a cubic bipartite polyhedral graph, and also constructible, then $P$ is Hamiltonian.

While I am aware that there are non 2-connected bipartite planar graphs, such as the tetrahedron with all edges subdivided, I cannot immediately come up with any non-constructible graphs that are also cubic and polyhedral.

Second edit: On further thought, an example is the (unique) cubic polyhedral graph with 6 squares and 3 hexagons. (constructed by having 2 clumps of 3 pairwise incident squares divided by a ring of hexagons)

  • 2
    $\begingroup$ Not an answer to your question, but I'll mention that Gunnar Brinkmann, Jan Goedgebeur and I have proved Barnette's conjecture up to 90 vertices inclusive. It isn't published yet. $\endgroup$ Feb 6, 2020 at 0:57
  • 1
    $\begingroup$ Exciting to hear! I read your earlier paper for 64 vertices. (Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs) In section 4, you cite fig. 16d as a counter-example to the claim that every Barnette graph has a Hamiltonian cycle that avoid the maximum independent set of edges for a given face. For quite some time, I have wondered if there exists a counter-example which lacks two incident squares; the answer to this is actually relevant to extending my methods. Do you happen to have an answer to this off the top of your head? $\endgroup$ Feb 6, 2020 at 1:34
  • 1
    $\begingroup$ I don't know. I'm very busy at the moment but feel free to write to me ([email protected]) in several weeks if you like. $\endgroup$ Feb 6, 2020 at 3:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.