Provable Hamiltonian Subclass of Barnette Graphs

153 Views Asked by At

Given a bicubic planar graph consisting of faces with degree $4$ and $6$, so called Barnette graphs. We can show that there are exactly six squares. Kundor and I found six types of arrangements of the six squares:

  1. three pairs of squares $(2+2+2)$
  2. two triples arranged in row $(\bar3+\bar3)$
  3. two triples arranged like a triangle $(3^\triangle+3^\triangle)$
  4. six isolated squares $(1+1+1+1+1+1)$
  5. two pairs and two isolated squares $(2+2+1+1)$
  6. one pair and four isolated squares $(2+1+1+1+1)$

Is there anything known if any of these arrangements can be proven to be Hamiltonian?

For example, "3. two triples arranged like a triangle" gives much less structural degrees of freedom compared to "4. six isolated squares"...