Hamiltonicity in vertex envelopes of plane cubic graphs

AbstractIn this paper we study a graph operation which produces what we call the “vertex envelope” G∗V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope