Suppose I have a non-Hamiltonian non-bipartite cubic planar graph $G_1$ = ($V_1$, $E_1$) where no face has fewer than five sides, and that I can partition $V_1$ into two Hamiltonian subgraphs. Suppose further that $G_1$ has a set of faces that satisfies the Grinberg equation (remember that satisfaction of the Grinberg equation is a necessary but not sufficient condition for a graph to be Hamiltonian), and is minimally two-connected, i.e., it contains exactly two edges, $v_1$ and $w_1$, whose removal disconnects $G_1$. Finally, assume that $G_1$ contains no separating triangles. Is there an example of such a $G_1$ that I can augment (judiciously) without limit by successively adding sets of vertices and edges to it in such a way that I create the series ($G_1$, $G_2$,...,$G_n$), |$V_i$| < |$V_j$|, n $\in$ $\mathbb{Z^+}$, where $G_i$ retains the given properties (including $v_1$and $w_1$) of $G_1$?

  • 2
    $\begingroup$ I'm not really sure what you mean by non-trivial, but Grinberg's theorem (en.wikipedia.org/wiki/Grinberg%27s_theorem) provides a way to make lots of 3-connected non-Hamiltonian cubic graphs without gadgets: just pack five- and eight-sided faces with three-fold symmetry so that the number of sides of the outer face is a multiple of three. $\endgroup$ – David Eppstein Feb 19 '15 at 4:08
  • $\begingroup$ I am aware of Grinberg’s theorem. I should have added that I am looking for a scalable non-Hamiltonian $G$ that satisfies his formulation. $\endgroup$ – user2749107 Feb 19 '15 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.