On Vertex Magic 3-Regular Graphs with a Perfect Matching

Let G=(V,E) be a finite simple graph with p=|V| vertices and q=|E| edges, without isolated vertices or isolated edges. A vertex magic total labeling is a bijection f from V∪E to the consecutive integers 1,2,…,p+q, with the property that, for every vertex u∈V, one has f(u)+∑uv∈Ef(uv)=k for some magic constant k. The vertex magic total labeling is called E-super if furthermore f(E)={1,2,…,q}. A graph is called (E-super) vertex magic if it admits an (E-super) vertex magic total labeling. In this paper, we verify the existence of E-super vertex magic total labeling for a class of 3-regular graphs with a perfect matching, and we confirm the existence of such a labeling for general regular graphs of odd degree containing particular classes of 3-factors, which provides us with known and new examples. Note that Harary graphs are among the popular models used in communication networks. In 2012, G. Marimuthu and M. Balakrishnan raised a conjecture that if n>4, n≡0(mod4) and m is odd, then the Harary graph Hm,n admits an E-super vertex magic labeling. Among others, we are able to verify this conjecture except for one case while m=3 and n≡4(mod8).