# On(a,1)-Vertex-Antimagic Edge Labeling of Regular Graphs

Authors: Martin Bača; Andrea Semaničová-Feňovčíková; Tao-Ming Wang; Guang-Hui Zhang
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

An(a,s)-vertex-antimagic edge labeling (or an (a,s)-VAE labeling, for short) of G is a bijective mapping from the edge set E(G) of a graph G to the set of integers 1,2,…,|E(G)| with the property that the vertex-weights form an arithmetic sequence starting from a and having common difference s, where a and s are two positive integers, and the vertex-weight is the sum of the labels of all edges incident to the vertex. A graph is called (a,s)-antimagic if it admits an (a,s)-VAE labeling. In this paper, we investigate the existence of (a,1)-VAE labeling for disconnected 3-regular graphs. Also, we define and study a new concept (a,s)-vertex-antimagic edge deficiency, as an extension of (a,s)-VAE labeling, for measuring how close a graph is away from being an (a,s)-antimagic graph. Furthermore, the (a,1)-VAE deficiency of Hamiltonian regular graphs of even degree is completely determined. More open problems are mentioned in the concluding remarks.


---

## Body

## 1. Background and Introduction

All graphs in this paper are finite simple, undirected, and possibly disconnected, but without any isolated vertex or any isolated edge. For graph theoretic notations, we follow [1]. Over the past few decades, many kinds of graph labelings have been studied intensively, and an excellent survey of graph labeling can be found in Gallian’s paper [2].Hartsfield and Ringel in [3] introduced the concept of anantimagic labeling. In their terminology, a (p,q)-graph G with p vertices and q edges is calledantimagic if its edges are labeled with labels 1,2,…,q in such a way that allvertex-weights are pairwise distinct, where a vertex-weight of vertex v is the sum of labels of all edges incident with v. Hartsfield and Ringel [3] pointed out that antimagic graphs include paths Pn, n≥3, cycles, wheels, and complete graphs Kn, n≥3. They conjecture that every connected graph, except K2, is antimagic. Alon et al. [4] used several probabilistic tools and some techniques from analytic number theory to show that this conjecture is true for all graphs having minimum degree Ω(log|V(G)|).In 1993, Bodendiek and Walther [5] investigated antimagic labelings with certain restriction placed on the vertex-weights. They defined the concept of an (a,s)-vertex-antimagic edge labeling as follows.Definition 1.
An(a,s)-vertex-antimagic edge labeling (or an (a,s)-VAE labeling for short) of a (p,q)-graph G is a bijective mapping f from the edge set E(G) of a graph G to the set of integers 1,2,…,q with the property that the vertex-weights form an arithmetic sequence starting from a and having common difference s, where a and s are two positive integers. The vertex-weight wtf(u) of the vertex u is the sum of the labels of all edges incident with the vertex u under the mapping f. A graph is called (a,s)-antimagic if it admits an (a,s)-VAE labeling.Bodendiek and Walther in [6, 7] proved that the Herschel graph is not (a,s)-VAE and obtained both positive and negative results about (a,s)-VAE labelings for various cases of graphs called parachutes Pα,β. They investigated (a,s)-VAE labelings for paths, cycles, and complete graphs in [8]. Characterization of all (a,s)-antimagic graphs of the prism Cn□P2 when n is even is given in [9]. In [10, 11] the (a,s)-VAE labelings for antiprisms have been investigated. It is proved in [12] that the generalized Petersen graph P(n,m) has an (a,1)-VAE labeling if and only if n is even, n≥4, 1≤m≤n/2-1, and a=(7n+4)/2. Nicholas et al. [13] obtained several results about (a,d)-VAE labelings for caterpillars, unicyclic graphs, and complete bipartite graphs.On the other hand, in 2002, MacDougall et al. [14] introduced the concept ofvertex magic total labeling as follows. If G is a finite simple undirected graph with p vertices and q edges, then a vertex magic total labeling is a bijection f from V(G)∪E(G) to the integers 1,2,…,p+q with the property that, for every u∈V(G), the sum f(u)+∑uv∈E(G)‍f(uv) is a constant. Note that, for regular graphs, the vertex magic total labeling is equivalent to the (a,1)-VAE labeling, while the vertices (edges) are assigned the smallest labels. More recently, Wang and Zhang [15] verified the existence of (a,1)-VAE labeling for particular classes of 3-regular graph H, where H contains a 1-factor and a 2-factor which consists of two 2-regular subgraphs with equal size. These results generalize and contain previous known examples such as Generalized Petersen Graphs.The following theorem was proved in [16] by Ivančo and Semaničová, which guarantees the existence of the (a,1)-VAE-ness by adding an arbitrary even factor to an arbitrary (a,1)-antimagic graph.Theorem 2 (see [16]).
Let the graphG admit an (a,1)-VAE labeling, and let H be any 2-factor over V(G). Then, G∪H still admits an (b,1)-VAE labeling for some b.Therefore in order to study the(a,1)-antimagicness of a general regular graph, based upon Theorem 2 and the fact, pointed out by Petersen [17], that any regular graph of even degree has a 2-factorization, it is natural to explore the (a,1)-antimagicness of 2-regular graphs and 3-regular graphs, respectively. In this paper, we in particular investigate the existence of (a,1)-VAE labeling for disconnected 3-regular graphs and also define a new concept (a,1)-VAE deficiency, as an extension of (a,1)-VAE labeling, for studying those (regular) graphs not admitting an (a,1)-VAE labeling. The (a,1)-VAE deficiency is a parameter to measure how close a graph is from being (a,1)-antimagic. We notice that the method employed here is also valid for those graphs with multiple edges and loops. More examples and open problems will be provided in Section 5.


## 2. Preliminary Results

SupposeG is a (p,q)-graph with p vertices and q edges. The following are necessary conditions for graphs to admit an (a,s)-VAE labeling and (a,1)-VAE labeling in particular.Lemma 3.
If a(p,q)-graph is (a,s)-antimagic, then q(q+1)=pa+s((p-1)p/2).Proof.
Consider that the total sum of all vertex-weights in(p,q)-graph is (1)21+2+⋯+q=a+a+s+⋯+a+sp-1by two-way counting, and it implies that q(q+1)=pa+s(p-1p/2).By Lemma3 and for s=1, in case q=p, then a=(p+3)/2. Note that a is a positive integer, which implies that p is odd. Furthermore, in the case q=p-1, one has a=(p-1)/2, which implies that p is odd. Therefore, we have the following properties for (a,1)-VAE-ness.Corollary 4.
LetG be a (p,p-1)-graph. If G is (a,1)-antimagic, then p is odd.Corollary 5.
Trees of even order are not(a,1)-antimagic. In particular, a path of even order is not (a,1)-antimagic.Corollary 6.
LetG be a (p,p)-graph. If G is (a,1)-antimagic, then p is odd.Corollary 7.
The even cycleC2n is not (a,1)-antimagic.Proposition 8.
LetG be an r-regular graph of order p and let G admit an (a,1)-VAE labeling. Then, we have the following: (1)
Ifr is odd, then p≡0(mod⁡4).(2)
Ifr is even, then p≡1(mod⁡2).Proof .
LetG have q edges. Then, by hand-shaking lemma, we have that pr=2q. Since G admits an (a,1)-VAE labeling, by Lemma 3, we have q(q+1)=pa+p-1p/2. Combining these equations, one has that a=(1+rp/2)(r/2)-(p-1)/2=(2r+r2p-2p+2)/4, which must be an integer. Therefore, it follows that if r is odd, then p≡0(mod⁡4), and if r is even, then p≡1(mod⁡2).


## 3.(a,1)-VAE for 3-Regular Graphs

In this section, we study the(a,1)-VAE labeling of disjoint union of 3-regular graphs. The main result is the following.Theorem 9.
LetG be an (a,1)-antimagic 3-regular graph having a perfect matching. Then, the disjoint union of arbitrary number of copies of G, that is, mG, m≥1, is also a (b,1)-antimagic graph.Proof.
LetG be a 3-regular graph with p vertices having a perfect matching.
Suppose thatG admits an (a,1)-VAE labeling f such that (2)f:EG⟶1,2,…,3p2,wtfv=∑uv∈EGfuv:v∈VG=a,a+1,…,a+p-1.
AsG contains a perfect matching, we can divide the edges of G into two subsets E1(G) and E2(G), such that (3)E1G∪E2G=EG,E1G∩E2G=∅,where the subset E1(G) consists of all edges belonging to the perfect matching.
For every vertexv in G, we denote by symbol vi the corresponding vertex in the ith copy of G in mG. Analogously, let ei=uivi denote the corresponding edge in the ith copy of G in mG.
Define the labelingf for the edges of mG in the following way: (4)gei=mfe-1+i,ife∈E2G,i=1,2,…m,mfe+1-i,ife∈E1G,i=1,2,…m.
Lett∈{1,2,…,3p/2}. We consider two cases.
Case 1. If the number t is assigned by the labeling f to an edge from E2(G), then the corresponding edges in the copies in mG will receive labels under the labeling g:(5)mt-1+1,mt-1+2,⋯mt-1+i,⋯mt.inG1inG2⋯inGi⋯inGm.
Case 2. If the number t is assigned by the labeling f to an edge from E1(G), then the corresponding edges in the copies in mG will have the following labels under the labeling g:(6)mt,mt-1,⋯mt+1-i,⋯mt-1+1.inG1inG2⋯inGi⋯inGm.
It is easy to see that the edge labels inmG are not overlapping; thus, the labeling g is a bijective function which assigns the integers {1,2,…,3mp/2} to the edges of mG; thus, g is an edge labeling.
AsG is a 3-regular graph with a perfect matching, then every vertex in G is incident to exactly one edge from E1(G) and exactly two edges from E2(G). For a given vertex v, let ev,11,ev,22,ev,32 be the three edges incident to the vertex v, where ej means that the edge belongs to the subset Ej(G), j=1,2.
For the vertex-weight ofvi∈V(Gi), we have (7)wtgvi=gev,11i+gev,22i+gev,32i=mfev,11+1-i+mfev,22-1+i+mfev,32-1+i=mfev,11+fev,22+fev,32-2m+1+i=mwtfv-2m+1+i=mwtfv-2+1+i.
As(8)wtfv=∑uv∈EGfuv:v∈VG=a,a+1,…,a+p-1,we get that the vertex-weights under the labeling g in the components are(9)G1:ma-2+2,ma-1+2,⋯ma+p-3+2,G2:ma-2+3,ma-1+3,⋯ma+p-3+3,⋮⋮⋮⋮Gi:ma-2+1+i,ma-1+1+i,⋯ma+p-3+1+i,⋮⋮⋮⋮Gm:ma-1+1,ma+1,⋯ma+p-2+1.
The reader can easily verify that the vertex-weights are distinct and consecutive:(10)wtgv:v∈VmG=ma-2+2,ma-2+3,…,ma+p-2+1.
This means thatmG has a (m(a-2)+2,1)-VAE labeling.It is possible to extend the result from the previous theorem also for the disjoint union of arbitrary 3-regular graphs having a perfect matching that satisfy certain additional conditions.We will follow the notation used in the proof of Theorem9.Theorem 10.
LetGi be an (a,1)-antimagic 3-regular graph of order p having a perfect matching, i=1,2,…,m. Let the set of all edge labels belonging to the perfect matching under the (a,1)-VAE labeling fi of a graph Gi be the same for every i, i=1,2,…,m.
Then, the disjoint union⋃i=1m‍Gi is also a (b,1)-antimagic graph.Proof.
LetGi, i=1,2,…,m, be a 3-regular graph of order p having a perfect matching, i=1,2,…,m, and note that Gi is not necessarily isomorphic to Gj for i≠j.
For eachGi, i=1,2,…,m, there exists an (a,1)-VAE labeling fi such that the set of all edge labels belonging to the perfect matching under the (a,1)-VAE labeling fi of a graph Gi is the same for every graph Gi. This means that(11)fi:E1Gi⟶t1,t2,…,tp/2E2Gi⟶1,2,…,3p/2t1,t2,…,tp/2,wtfiv=∑uv∈EGifuv:v∈VGi=a,a+1,…,a+p-1.
We define the labelingf for the edges of ⋃i=1m‍Gi in the following way: (12)fe=mfie-1+i,ife∈E2Gi,mfie+1-i,ife∈E1Gi.
Lett∈{1,2,…,3p/2}. We consider two cases.
Case 1. If the number t is assigned by the labeling fi to an edge from E2(Gi), then the corresponding edge in ⋃i=1m‍Gi will receive the following label under the labeling f:(13)mt-1+1,mt-1+2,⋯mt-1+i,⋯mt.inG1inG2⋯inGi⋯inGm.
Case 2. If the number t is assigned by the labeling fi to an edge from E1(Gi), then the corresponding edge in ⋃i=1m‍Gi will receive this label under the labeling f:(14)mt,mt-1,⋯mt+1-i,⋯mt-1+1.inG1inG2⋯inGi⋯inGm.
It is easy to see that the edge labels in⋃i=1m‍Gi are not overlapping; thus, the labeling f is a bijective function which assigns the integer {1,2,…,3mp/2} to the edges of ⋃i=1m‍Gi; thus, f is an edge labeling.
Moreover, analogously as in the proof of Theorem9, we get that the vertex-weights form an arithmetic sequence with a difference 1. This produces the desired result.


## 4.(a,1)-VAE Deficiency of Even Regular Graphs

We start this section by defining a new concept(a,s)-vertex-antimagic edge deficiency for a (p,q)-graph G as follows. It is a parameter to study furthermore those graphs which do not admit any (a,s)-VAE labeling and to measure how close they are away from being an (a,s)-antimagic graph.Definition 11.
The(a,s)-vertex-antimagic edge deficiency (or (a,s)-VAE deficiency for short) is defined as the min⁡k such that the edge labeling f:E(G)→{1,2,…,q+k} is (a,s)-VAE. The (a,s)-VAE deficiency of the graph G is denoted by ds(G). Note that ds(G)=0 if G is (a,s)-antimagic and ds(G)=+∞ if no such k exists for the graph G to be (a,s)-antimagic.In the following, we determine completely the(a,1)-VAE deficiency of paths and cycles. Also, as a corollary, the (a,1)-VAE deficiency of Hamiltonian regular graphs of even degree is obtained. First, we have the following two lemmas giving (a,1)-VAE labelings for odd cycles and paths; see also [8].Lemma 12.
The cycleC2n+1 is (a,1)-antimagic for n≥1.Proof.
Given a notation forC2n+1 with V(C2n+1)={vi:i=1,2,…,2n+1} and E(C2n+1)={vivi+1:i=1,2,…,2n}∪{v1v2n+1}, we give an edge labeling f for E(C2n+1) with (15)fv1v2n+1=n+1,fvivi+1=i+12,ifi=1,3,…,2n-1,n+1+i2,ifi=2,4,…,2nand it implies the vertex-weight at vi as follows: (16)wtfvi=n+1+i,fori=1,2,…,2n+1.Hence, C2n+1 is (n+2,1)-antimagic.Lemma 13.
The pathP2n+1 is (a,1)-antimagic for n≥1.Proof.
Given a notation forP2n+1 with V(P2n+1)={vi:i=1,2,…,2n+1} and E(P2n+1)={vivi+1:i=1,2,…,2n}, we give an edge labeling f for E(P2n+1) such that (17)fvivi+1=i2,ifi=2,4,…,2n,n+i+12,ifi=1,3,…,2n-1and it implies the vertex-weight at vi as follows:(18)wtfvi=n+i,ifi=1,2,…,2n,n,ifi=2n+1.Hence, P2n+1 is (n,1)-antimagic.Here, we have a general observation that every graphG of order p, where p≡2(mod⁡4), can not be made (a,1)-antimagic.Lemma 14.
LetG be a graph of order p, where p≡2(mod⁡4). Then, d1(G)=+∞.Proof.
LetG have q edges and p=4k+2 vertices. Assign labels e1,e2,…,eq to edges of graph G and suppose the existence of an (a,1)-VAE labeling with the associated vertex-weights a,a+1,…,a+(4k+1). Consider the sum of all vertex-weights: (19)a+a+1+⋯+a+4k+1=4k+2a+4k+12k+1which is also equal to 2(e1+e2+⋯+eq). Note that 2(e1+e2+⋯+eq) and (4k+2)a are both even, but (4k+1)(2k+1) is odd, a contradiction.In the following lemmas, we are dealing with the(a,1)-VAE deficiency of cycles and paths.Lemma 15.
Considerd1(C4n)=1 for n≥1.Proof.
First, we find the missing valuex in the set of edge labels {1,2,…,4n}. Note that (20)21+2+⋯+4n+1-x=a+a+1+⋯+a+4n-1and it implies a=(4n2+7n+1-x)/2n=2n+3+(n+1-x)/2n∈Z and thus (n+1-x)/2n∈Z. Suppose that (n+1-x)/2n=t, and then one has -n≤-2nt≤3n-1 since 1≤x≤4n. Therefore, t must be 0 or -1, and it implies that the missing value x must be n+1 or 3n+1. We show that for both missing values there exist (a,1)-VAE labelings.
Let the vertex set and the edge set ofC4n be V(C4n)={vi:i=1,2,…,4n} and E(C4n)={vivi+1:i=1,2,…,4n-1}∪{v1v4n}.
Case 1. If the missing value is n+1, then the (a,1)-VAE labeling can be defined as follows: (21)f1v1v4n=4n+1,f1vivi+1=i+12,ifi=1,3,…,2n-1,i+32,ifi=2n+1,2n+3,…,4n-1,2n+1+i2,ifi=2,4,…,4n-2.
Case 2. If the missing value is 3n+1, then, for example, consider the following edge labeling: (22)f2v1v4n=4n+1,f2vivi+1=i+12,ifi=1,3,…,4n-1,2n+i2,ifi=2,4,…,2n,2n+1+i2,ifi=2n+2,2n+4,…,4n-2.Then, we find that the vertex-weights form the set {2n+3,2n+4,…,6n+2} for Case 1 and the set {2n+2,2n+3,…,6n+1} for Case 2. Hence, d1(C4n)=1 as required.Lemma 16.
Considerd1(P4n)=1 for n≥1.Proof.
First, we suppose thatd1(P4n)≤1 and we want to find the missing value x in the set of edge labels {1,2,…,4n-1}. Then, (23)21+2+⋯+4n-x=a+a+1+⋯+a+4n-1and it implies that a=(4n2+3n-x)/2n=2n+1+(n-x)/2n and thus (n-x)/2n∈Z. Suppose that (n-x)/2n=t, and then 1-n≤-2nt≤3n-1, since 1≤x≤4n-1. Therefore, t must be 0 or -1 and it implies that the missing value is x=n or 3n. As in the proof of the previous lemma we show that for both cases it is possible to find required (a,1)-VAE labelings.
We denote the vertices and the edges ofP4n such that V(P4n)={vi:i=1,2,…,4n} and E(P4n)={vivi+1:i=1,2,…,4n-1}.
Case 1. If the missing value is n, then we define the edge labeling f3 in the following way: (24)f3vivi+1=2n+i+12,ifi=1,3,…,4n-1,i2,ifi=2,4,…,2n-2,1+i2,ifi=2n,2n+2,…,4n-2.
Case 2. If the missing value is 3n, then we define the labeling f4 such that (25)f4vivi+1=2n+i-12,ifi=1,3,…,2n-1,2n+i+12,ifi=2n+1,2n+3,…,4n-1,i2,ifi=2,4,…,4n-2.
Then, we obtain that the vertex-weights attain the values from the sets{2n+1,2n+2,…,6n} for Case 1 and {2n,2n+3,…,6n-1} for Case 2. Thus, d1(P4n)=1.To summarize, we have the following(a,1)-VAE deficiency for paths Pm and cycles Cm.Theorem 17.
Letm≥2. Then, (26)d1Pm=0,ifm≡1,3mod⁡4,1,ifm≡0mod⁡4,+∞,ifm≡2mod⁡4.Theorem 18.
Letm≥3. Then, (27)d1Cm=0,ifm≡1,3mod⁡4,1,ifm≡0mod⁡4,+∞,ifm≡2mod⁡4.Therefore, as a corollary of Theorem18, we immediately have the following result.Theorem 19.
LetG be a 2r-regular, r≥2, Hamiltonian graph of order p. Then, (28)d1G=0,ifp≡1,3mod⁡4,1,ifp≡0mod⁡4,+∞,ifp≡2mod⁡4.Proof.
By Theorem18, Lemma 12, Theorem 2, and also Petersen’s 2-factorization of regular graphs of even degree, we get that a Hamiltonian even regular graph of odd order is (a,1)-antimagic. On the other hand, by Lemma 15 and Theorem 2, we get that the Hamiltonian even regular graphs of order 4n have the (a,1)-VAE deficiency equal to 1. Finally, by Lemma 14, we complete the proof.As a corollary, we have the following example of(a,1)-VAE deficiency for the Cartesian product of two cycles Cm□Cn,m,n≥3. Note that Cm□Cn always contains a Hamiltonian cycle.Corollary 20.
Letm,n≥3. Then, (29)d1Cm□Cn=0,ifmn≡1,3mod⁡4,1,ifmn≡0mod⁡4,+∞,ifmn≡2mod⁡4.Note that similarly one may have the formula for(a,1)-VAE deficiency of the higher dimensional toroidal grids, that is, the Cartesian product of t cycles Cm1□Cm2□⋯□Cmt,mi≥3, for each i.


## 5. Concluding Remarks and Further Studies

Notice that in 2009 Holden et al. [18] raised a conjecture for the existence of (a,1)-VAE labeling of 2-regular graphs as follows: a 2-regular graph of odd order possesses an (a,1)-VAE labeling if and only if it is not one of C4∪C3, C4∪3C3, or C5∪2C3. Note that the terminology of the labeling they made is the strong vertex magic total labeling, which is exactly equivalent to the (a,1)-VAE labeling. Therefore, it is natural to ask for the following.Problem 1.
Determine the(a,1)-VAE deficiency for C4∪C3, C4∪3C3, and C5∪2C3.Moreover, as a generalization of the above result, we obtain in the last section the(a,1)-VAE deficiency of a Hamiltonian regular graph of even degree, and we are concerned with the following situation. Note that Swaminathan and Jeyanthi [19] pointed out the following: mCn is (a,1)-antimagic if and only if m,n are odd. Therefore, it is natural to ask for the following.Problem 2.
Determine the(a,1)-VAE deficiency for the 2-regular graph mCn.If Problem2 is answered, then the (a,1)-VAE deficiency for an arbitrary regular graph of even degree containing a 2-factor mCn is answered. More generally, we have the following.Problem 3.
Determine the(a,1)-VAE deficiency for a general 2-regular graph.If Problem3 is answered, then the (a,1)-VAE deficiency for an arbitrary regular graph of even degree is answered. As for 3-regular graphs and general odd regular graphs, we ask for the following.Problem 4.
Determine the(a,1)-VAE deficiency for 3-regular Generalized Petersen Graphs P(n,k) and Mo¨bius Ladder Graphs Mn.Problem 5.
Determine the(a,1)-VAE deficiency for a general 3-regular graph.Problem 6.
Determine the(a,1)-VAE deficiency for a general odd regular graph.It is not hard to check thatK4 does not admit any (a,1)-VAE labeling. However, with the aid of computer programs, we have found that tK4 admits an (a,1)-VAE labeling for 2≤t≤9. This leads to the following conjecture.Conjecture 21.
t
K
4, the disjoint union of t copies of K4, admits the (a,1)-VAE labeling for t≥2.



---

*Source: 320616-2015-06-08.xml*