# New Results on the (Super) Edge-Magic Deficiency of Chain Graphs

Authors: Ngurah Anak Agung Gede; Adiwijaya
Journal: International Journal of Mathematics and Mathematical Sciences
 (2017)

---

## Abstract

LetG be a graph of order v and size e. Anedge-magic labeling of G is a bijection f:V(G)∪E(G)→{1,2,3,…,v+e} such that f(x)+f(xy)+f(y) is a constant for every edge xy∈E(G). An edge-magic labeling f of G with f(V(G))={1,2,3,…,v} is called asuper edge-magic labeling. Furthermore, theedge-magic deficiency of a graph G, μ(G), is defined as the smallest nonnegative integer n such that G∪nK1 has an edge-magic labeling. Similarly, thesuper edge-magic deficiency of a graph G, μs(G), is either the smallest nonnegative integer n such that G∪nK1 has a super edge-magic labeling or +∞ if there exists no such integer n. In this paper, we investigate the (super) edge-magic deficiency of chain graphs. Referring to these, we propose some open problems.


---

## Body

## 1. Introduction

LetG be a finite and simple graph, where V(G) and E(G) are its vertex set and edge set, respectively. Let v=|V(G)| and e=|E(G)| be the number of the vertices and edges, respectively. In [1], Kotzig and Rosa introduced the concepts of edge-magic labeling and edge-magic graph as follows: anedge-magic labeling of a graph G is a bijection f:V(G)∪E(G)→{1,2,3,…,v+e} such that f(x)+f(xy)+f(y) is a constant, called themagic constant of f, for every edge xy of G. A graph that admits an edge-magic labeling is called anedge-magic graph. Asuper edge-magic labeling of a graph G is an edge-magic labeling f of G with the extra property that f(V(G))={1,2,3,…,e}. Asuper edge-magic graph is a graph that admits a super edge-magic labeling. These concepts were introduced by Enomoto et al. [2] in 1998.In [1], Kotzig and Rosa introduced the concept of edge-magic deficiency of a graph. They define theedge-magic deficiency of a graph G, μ(G), as the smallest nonnegative integer n such that G∪nK1 is an edge-magic graph. Motivated by Kotzig and Rosa’s concept of edge-magic deficiency, Figueroa-Centeno et al. [3] introduced the concept of super edge-magic deficiency of a graph. Thesuper edge-magic deficiency of a graph G, μs(G), is defined as the smallest nonnegative integer n such that G∪nK1 is a super edge-magic graph or +∞ if there exists no such n.Achain graph is a graph with blocks B1,B2,…,Bk such that, for every i, Bi and Bi+1 have a common vertex in such a way that the block-cut-vertex graph is a path. We will denote the chain graph with k blocks B1,B2,…,Bk by C[B1,B2,…,Bk]. If B1=⋯=Bt=B, we will write C[B1,B2,…,Bk] as C[B(t),Bt+1,…,Bk]. If, for every i, Bi=H for a given graph H, then C[B1,B2,…,Bk] is denoted by kH-path. Suppose that c1,c2,…,ck-1 are the consecutive cut vertices of C[B1,B2,…,Bk]. Thestring of C[B1,B2,…,Bk] is (k-2)-tuple (d1,d2,…,dk-2), where di is the distance between ci and ci+1, 1≤i≤k-2. We will write (d1,d2,…,dk-2) as (d(t),dt+1,…,dk-2), if d1=⋯=dt=d.For any integerm≥2, let Lm=Pm×P2. Let TLm and DLm be the graphs obtained from the ladder Lm by adding a single diagonal and two diagonals in each rectangle of Lm, respectively. Thus, |V(TLm)|=|V(DLm)|=2m, |E(TLm)|=4m-3, and |E(DLm)|=5m-4. TLm and DLm are called triangle ladder and diagonal ladder, respectively.Recently, the author studied the (super) edge-magic deficiency ofkDLm-path, C[K4(k),DLm,K4(n)], and kC4-path with some strings. Other results on the (super) edge-magic deficiency of chain graphs can be seen in [4]. The latest developments in this area can be found in the survey of graph labelings by Gallian [5]. In this paper, we further investigate the (super) edge-magic deficiency of chain graphs whose blocks are combination of TLm and DLm and K4 and TLm, as well as the combination of C4 and Lm. Additionally, we propose some open problems related to the (super) edge-magic deficiency of these graphs. To present our results, we use the following lemmas.Lemma 1 (see [6]).
A graphG is a super edge-magic graph if and only if there exists a bijective function f:V(G)→{1,2,…,v} such that the set S={f(x)+f(y):xy∈E(G)} consists of e consecutive integers.Lemma 2 (see [2]).
IfG is a super edge-magic graph, then e≤2v-3.


## 2. Main Results

Fork≥3, let G=C[B1,B2,…,Bk], where Bj=TLm when j is odd and Bj=DLm when j is even. Thus G is a chain graph with |V(G)|=(2m-1)k+1 and |E(G)|=(1/2)(k+1)(4m-3)+(1/2)(k-1)(5m-4) when k is odd, or |E(G)|=(k/2)(4m-3)+(k/2)(5m-4) when k is even. By Lemma 2, it can be checked that G is not super edge-magic when m≥3 and k is even and when m≥4 and k is odd. As we can see later, when m=3 and k is odd, G is super edge-magic. Next, we investigate the super edge-magic deficiency of G. Our first result gives its lower bound. This result is a direct consequence of Lemma 2, so we state the result without proof.Lemma 3.
Letk≥3 be an integer. For any integer m≥3, (1)μsG≥14km-3+1,ifkiseven,14km-3-m-1+1,ifkisodd.Notice that the lower bound presented in Lemma3 is sharp. We found that when m is odd, the chain graph G with particular string has the super edge-magic deficiency equal to its lower bound as we state in Theorem 4. First, we define vertex and edge sets of Bj as follows.V
(
B
j
)
=
{
u
j
i
,
v
j
i
:
1
≤
i
≤
m
}, for 1≤j≤k.  E(Bj)={ujiuji+1,vjivji+1:  1≤i≤m-1}∪{eji:  whereejiiseitherujivji+1orvjiuji+1,1≤i≤m-1}∪{ujivji:  1≤i≤m}, for 1≤j≤k, when j is odd, and E(Bj)={ujiuji+1,vjivji+1,ujivji+1,vjiuji+1:1≤i≤m-1}∪{ujivji:1≤i≤m}, for 1≤j≤k, when j is even.Theorem 4.
Letk≥3 be an integer and G=C[B1,B2,…,Bk] with string (m-1,d1,m-1,d2,m-1,…,d(1/2)(k-3),m-1) when k is odd or (m-1,d1,m-1,d2,…,m-1,d(1/2)(k-2)) when k is even, where d1,d2,…,d(1/2)(k-2)∈{m-1,m}. For any odd integer m≥3,(2)μsG=14km-3+1,ifkiseven,14k-1m-3,ifkisodd.Proof.
First, we defineG as a graph with vertex set V(G)=⋃j=1kV(Bj), where ujm=vj+11, 1≤j≤k-1, and edge set E(G)=⋃j=1kE(Bj). Under this definition, ujm=vj+11, 1≤j≤k-1, are the cut vertices of G.
Next, for1≤i≤m and 1≤j≤k, define the labeling f:V(G)∪αK1→{1,2,3,…,(2m-1)k+1+α}, where α=(1/4)k(m-3)+1 when k is even or α=(1/4)(k-1)(m-3) when k is odd, as follows:(3)fx=14j-19m-7+2i-1,ifx=uji,jisodd,14j-19m-7+2i,ifx=vji,jisodd,β+125i-3,ifx=uji,iisodd,jiseven,β+125i-4,ifx=uji,iiseven,jiseven,β+125i-7,ifx=vji,iisodd,jiseven,β+125i-6,ifx=vji,iiseven,jiseven,where β=(1/4)(j-2)(9m-7)+2m.
Under the vertex labelingf, it can be checked that no labels are repeated, f(ujm)=f(vj+11), 1≤j≤k-1, {f(x)+f(y):xy∈E(G)} is a set of |E(G)| consecutive integers, and the largest vertex label used is (1/4)(k-2)(9m-7)+(1/2)(9m-3) when k is even or (1/4)(k-1)(9m-7)+2m when k is odd. Also, it can be checked that f(uji)+f(vji+1)=f(vji)+f(uji+1) when j is odd.
Next, label the isolated vertices in the following way.
Case
k
Is Odd. In this case, we denote the isolated vertices with z2j-1l∣1≤l≤(1/2)(m-3),1≤j≤(1/2)(k-1)} and set f(z2j-1l)=f(v2j-1m)+5l.
Case
k
Is Even. In this case, we denote the isolated vertices with z2j-1l∣1≤l≤1/2m-3,1≤j≤k/2∪{z0} and set f(z2j-1l)=f(v2j-1m)+5l and f(z0)=f(vkm)+1.
By Lemma1, f can be extended to a super edge-magic labeling of G∪αK1 with the magic constant (k/4)(27m-21)+5 when k is even or (1/4)(k-1)(27m-21)+6m when k is odd. Based on these facts and Lemma 3, we have the desired result.An example of the labeling defined in the proof of Theorem4 is shown in Figure 1(a).Figure 1
(a) Vertex labeling ofC[TL5,DL5,TL5,DL5,TL5]∪2K1 with string (4, 5, 4). (b) Vertex and edge labelings of c[C4(3+2),L4,C4(2)] with string (2,1(2),2,4,2).
(a)
(b)Notice that whenm=3 and k is odd, μs(G)=0. In other words, the chain graph G with string (2,d1,2,d2,2,…,d(1/2)(k-3),2), where di∈{2,3}, is super edge-magic when m=3 and k is odd. Based on this fact and previous results, we propose the following open problems.Open Problem 1.
Letk≥3 be an integer. For m=2, decide if there exists a super edge-magic labeling of G. Further, for any even integer m≥2, find the super edge-magic deficiency of G.Next, we investigate the super edge-magic deficiency of the chain graphH=C[K4(p),TLm,K4(q)] with string (1(p-1),d,1(q-1)), where d∈{m-1,m}. H is a graph of order 3(p+q)+2m and size 6(p+q)+4m-3. We define the vertex and edge sets of H as follows: V(H)={ai,bi:  1≤i≤p}∪{ci:  1≤i≤p+1}∪{uj,vj:  1≤j≤m}∪{xt,yt:  1≤t≤q}∪{zt:  1≤t≤q+1}, where cp+1=u1 and vm=z1, and E(H)={aibi,aici,aici+1,bici,bici+1,cici+1:  1≤i≤p}∪ujvj∣1≤j≤m∪{ujuj+1,vjvj+1:  1≤j≤m-1}∪{ej:  ejiseitherujvj+1orvjuj+1,1≤j≤m-1}  ∪  {xtyt,xtzt,xtzt+1,ytzt,ytzt+1,ztzt+1:  1≤t≤q}. Hence, the cut vertices of H are ci, 2≤i≤p+1, and zt, 1≤t≤q. Notice that H has string (1(p-1),m-1,1(q-1)), if at least one of ej is ujvj+1, and its string is (1(p-1),m,1(q-1)), if ej=vjuj+i for every 1≤j≤m-1.Theorem 5.
For any integersp,q≥1 and m≥2, μs(H)=0.Proof.
Define a bijective functiong:V(H)→{1,2,3,…,3(p+q)+2m} as follows:(4)gx=3i-2,ifx=ai,1≤i≤p,3i,ifx=bi,1≤i≤p,3i-1,ifx=ci,1≤i≤p+1,3p+2j,ifx=uj,1≤j≤m,3p+2j-1,ifx=vj,1≤j≤m,3p+2m+3t-2,ifx=xt,1≤t≤q,3p+2m+3t,ifx=yt,1≤t≤q,3p+2m+3t-4,ifx=zt,1≤t≤q+1.
Under the labelingg, it can be checked that g(cp+1)=g(u1) and g(vm)=g(z1). Also, it can be checked that g(uj)+g(vj+1)=g(vj)+g(uj+1), 1≤j≤m-1, and gx+gy∣xy∈EH={3,4,5,…,6(p+q)+4m-1}. By Lemma 1, g can be extended to a super edge-magic labeling of H with the magic constant 9(p+q)+6m. Hence, μs(H)=0.Open Problem 2.
For any integersp,q≥1 and m≥2, find the super edge-magic deficiency of C[K4(p),TLm,K4(q)] with string (1(p-1),d,1(q-1)), where d∈{1,2,3,…,m-2}.Next, we study the edge-magic deficiency of ladderLm and chain graphs whose blocks are combination of C4 and Lm with some strings. In [6], Figueroa-Centeno et al. proved that the ladder Lm is super edge-magic for any odd m and suspected that Lm is super edge-magic for any even m>2. Here, we can prove that Lm is edge-magic for any m≥2 by showing its edge-magic deficiency is zero. The result is presented in Theorem 6.Theorem 6.
For any integerm≥2, μ(Lm)=0.Proof.
LetV(Lm)={ui,vi:1≤i≤m} and E(G)={uiui+1,vivi+1:  1≤i≤m-1}∪{uivi:1≤i≤m} be the vertex set and edge set, respectively, of Lm. It is easy to verify that the labeling h:V(Lm)∪E(Lm)→{1,2,3,…,5m-2} is a bijection and, for every xy∈E(Lm), h(x)+h(xy)+h(y)=6m.(5)hx=i,ifx=ui,iisodd,3m+12i-2,ifx=ui,iiseven,m+12i+1,ifx=vi,iisodd,i,ifx=vi,iiseven,3m-123i-1,ifx=uiui+1,iisodd,3m-32i,ifx=uiui+1,iiseven,5m-32i+1,ifx=vivi+1,iisodd,5m-123i+2,ifx=vivi+1,iiseven,5m-123i+1,ifx=uivi,iisodd,3m-123i-2,ifx=uivi,iiseven.Thus, μ(Lm)=0 for every m≥2.Theorem 7.
Letp and q≥1 be integers.(a)
Ifm≥2 is an even integer and F1=C[C4(p),Lm,c4(q)] with string (2(p-1),m,2(q-1)), then μ(F1)=0.(b)
Ifm≥3 is an odd integer and F2=C[C4(p),Lm,c4(q)] with string (2(p-1),m-1,2(q-1)), then μ(F2)=0.Proof.
(a) First, we introduce a constantλ as follows: λ=1, if m is odd and λ=2, if m is even. Next, we define F1 as a graph with V(F1)={ai,bi:  1≤i≤p}∪{ci:  1≤i≤p+1}∪{uj,vj:  1≤j≤m}∪{xt,yt:  1≤t≤q}∪{zt:  1≤t≤q+1}, where cp+1=v1 and um=z1, and E(H)={ciai,cibi,aici+1,bici+1:  1≤i≤p}∪ujvj∣1≤j≤m∪{ujuj+1,vjvj+1:  1≤j≤m-1}∪{ztxt,ztyt,xtzt+1,ytzt+1:  1≤t≤q}. The cut vertices of F1 are ci, 2≤i≤p+1, and zt, 1≤t≤q.
Next, define a bijectionf1:V(F1)∪E(F1)→{1,2,3,…,7(p+q)+5m-2} as follows:(6)f1x=4p+q+3m+i-1,ifx=ai,1≤i≤p,p+q+m+i,ifx=bi,1≤i≤p,i,ifx=ci,1≤i≤p+1,5p+4q+3m+12j-1,ifx=uj,jisodd,p+j,ifx=uj,jiseven,p+j,ifx=vj,jisodd,2p+q+m+j2,ifx=vj,jiseven,5p+4q+γ1+t,ifx=xt,1≤t≤q,2p+q+γ2+t,ifx=yt,1≤t≤q,p+m+t-1,ifx=zt,1≤t≤q+1,4p+q+3m+1-2i,ifx=ciai,1≤i≤p,7p+q+5m-2i,ifx=cibi,1≤i≤p,4p+q+3m-2i,ifx=aici+1,1≤i≤p,7p+q+5m-1-2i,ifx=bici+1,1≤i≤p,2p+4q+3m-123j+1,ifx=ujuj+1,jisodd,2p+4q+3m-123j,ifx=ujuj+1,jiseven,5p+7q+5m-123j+1,ifx=vjvj+1,jisodd,5p+7q+5m-123j+2,ifx=vjvj+1,jiseven,2p+4q+3m-123i-1,ifx=ujvj,jisodd,5p+7q+5m-32j,ifx=ujvj,jiseven,2p+4q+γ3-2tifx=ztxt,1≤t≤q,5p+7q+γ4-2t,ifx=ztyt,1≤t≤q,2p+4q+γ5-2t,ifx=xtzt+1,1≤t≤q,5p+7q+γ6-2t,ifx=ytzt+1,1≤t≤q,where γ1=(1/2)(λ-1)(7m-2)-(1/2)(λ-2)(7m-1), γ2=(1/2)(λ-1)(3m)-(1/2)(λ-2)(3m-1), γ3=(1/2)(λ-1)(3m+4)-(1/2)(λ-2)(3m+3), γ4=(1/2)(λ-1)(7m+2)-(1/2)(λ-2)(7m+3), γ5=(1/2)(λ-1)(3m+2)-(1/2)(λ-2)(3m+1), and γ6=(1/2)(λ-1)(7m)-(1/2)(λ-2)(7m+1). It is easy to verify that, for every edge xy∈E(F1), f(x)+f(xy)+f(y)=8(p+q)+6m.
(b) We defineF2 as graph with V(F2)=V(F1), where cp+1=v1 and vm=z1, and E(F2)=E(F1). Under this definition, the cut vertices of F2 are ci, 2≤i≤p+1, and zt, 1≤t≤q. Next, we define a bijection f2:V(F2)∪E(F2)→{1,2,3,…,7(p+q)+5m-2}, where f2(x)=f1(x) for all x∈V(F2)∪E(F2). It can be checked that f2 is an edge-magic labeling of F2 with the magic constant 8(p+q)+6m.Open Problem 3.
Letp and q≥1 be integers.(a)
Ifm≥3 is an odd integer, find the super edge-magic deficiency of C[C4(p),Lm,c4(q)] with string (2(p-1),m,2(q-1)).(b)
Ifm≥2 is an even integer, find the super edge-magic deficiency of C[C4(p),Lm,c4(q)] with string (2(p-1),m-1,2(q-1)).Theorem 8.
Letp,q≥2 and r≥1 be integers.(a)
Ifm≥2 is an even integer and H1=C[C4(p+q),Lm,c4(r)] with string (2(p-2),1(2),2(q-1),m,2(r-1)), then μ(H1)=0.(b)
Ifm≥3 is an odd integer and H2=C[C4(p+q),Lm,c4(r)] with string (2(p-2),1(2),2(q-1),m-1,2(r-1)), then μ(H2)=0.Proof.
(a) First, we defineH1 as a graph with V(H1)={ai:  1≤i≤2p}∪{bi:  1≤i≤p+1}∪{uj:  1≤j≤2q}∪{vj:  1≤j≤q+1}∪{ws:  1≤s≤2m}∪{xt:  1≤t≤2r}∪{yt:  1≤t≤r+1}, where a2p=u1, vq+1=w1, and w2m=y1, and E(H1)={biai,biap+i,aibi+1,ap+ibi+1:  1≤i≤p}  ∪  vjuj,vjuq+j,ujvj+1,uq+jvj+1∣1≤j≤q  ∪  {wsws+1,wm+swm+s+1 :  1≤s≤m-1}∪{wswm+s:  1≤s≤m}∪{ytxt,ytxr+t,xtyt+1,xr+tyt+1:  1≤t≤r}.
Next, define a bijectiong1:V(H1)∪E(H1)→{1,2,3,…,7(p+q+r)+5m-2} as follows:(7)g1z=6p+7q+r+5m+i-2,ifz=ai,1≤i≤p,3p+q+r+m+1+i,ifz=ap+i,1≤i≤p,i,ifz=bi,1≤i≤p+1,4p+q+r+m+j,ifz=uj,1≤j≤q,4p+q+r+3m+j-1,ifz=uq+j,1≤j≤q,p+1+j,ifz=vj,1≤j≤q+1,p+q+1+s,ifz=ws,sisodd,4p+2q+r+m+12s,ifz=ws,siseven,4p+5q+4r+3m+12s-1,ifz=wm+s,sisodd,p+q+1+s,ifz=wm+s,siseven,g1z=4p+2q+r+γ2+t,ifz=xt,1≤t≤r,4p+5q+4r+γ1+t,ifz=xr+t,1≤t≤r,p+q+m+t,ifz=yt,1≤t≤r+1,3p+q+r+m+3-2i,ifz=biai,1≤i≤p,6p+7q+r+5m-2i,ifz=biap+i,1≤i≤p,3p+q+r+m+2-2i,ifz=aibi+1,1≤i≤p,6p+7q+r+5m-2i-1,ifz=ap+ibi+1,1≤i≤p,4p+7q+r+5m-2j,ifz=vjuj,1≤j≤q,4p+q+r+3m+1-2j,ifz=vjuq+j,1≤j≤q,4p+7q+r+5m-2j-1,ifz=ujvj+1,1≤j≤q,4p+q+r+3m-2j,ifz=uq+jvj+1,1≤j≤q,4p+5q+7r+5m-123s+1,ifz=wsws+1,sisodd,4p+5q+7r+5m-123s+2,ifz=wsws+1,siseven,4p+2q+4r+3m-123s+1,ifz=wm+swm+s+1,sisodd,4p+2q+4r+3m-123s,ifz=wm+swm+s+1,siseven,4p+2q+4r+3m-123s-1,ifz=wswm+s,sisodd,4p+5q+7r+5m-32s,ifz=wswm+s,siseven,4p+5q+7r+γ4-2t,ifz=ytxt,1≤t≤r,4p+2q+4r+γ3-2t,ifz=ytxr+t,1≤t≤r,4p+5q+7r+γ6-2t,ifz=xtyt+1,1≤t≤r,4p+2q+4r+γ5-2t,ifz=xr+tyt+1,1≤t≤r,where γ1, γ2, γ3, γ4, γ5, γ6, and λ are defined as in the proof of Theorem 7. It can be checked that, for every edge xy∈E(H1), g1(x)+g1(xy)+g1(y)=9p+8(q+r)+6m+1. Hence μ(H1)=0.
An illustration of the labeling defined in the proof of Theorem8 is given in Figure 1(b).
(b) We defineH2 as graph with V(H2)=V(H1), where a2p=u1, vq+1=w1, and wm=y1, and E(H2)=E(H1). It can be checked that g2:V(H2)∪E(H2)→{1,2,3,…,7(p+q+r)+5m-2} defined by g2(x)=g1(x), for all x∈V(H2)∪E(H2), is an edge-magic labeling of H2 with the magic constant 9p+8(q+r)+6m+1.Open Problem 4.
Letp,q≥2 and r≥1 be integers.(a)
Ifm≥3 is an odd integer, find the edge-magic deficiency of C[C4(p),c4(q),Lm,c4(r)] with string (2(p-2),1(2),2(q-1),m,2(r-1)).(b)
Ifm≥2 is an even integer, find the edge-magic deficiency of C[C4(p),c4(q),Lm,c4(r)] with string (2(p-2),1(2),2(q-1),m-1,2(r-1)).



---

*Source: 5156974-2017-07-12.xml*