Vertex-Magic Cubic Graphs

Abstract

Let $G_1$ and $G_2$ be any two 2-regular graphs, each with $n$ vertices. Let $G$ be any cubic graph obtained from $G_1$ and $G_2$ by adding $n$ edges, each of which joins a vertex in $G_1$ to a vertex in $G_2$. We show that $G$ has a myriad of vertex-magic total labelings, with at least three different magic constants. This class of cubic graphs includes all generalized Petersen graphs.