# Star-Supermagic Decompositions of the Complete Bipartite Graph Minus a One-Factor

Authors: Tanawat Wichianpaisarn; Uthoomporn Mato
Journal: International Journal of Mathematics and Mathematical Sciences
 (2017)

---

## Abstract

LetG be a graph and let H be a subgraph of G. Assume that G has an H-decomposition T={H1,H2,…,Ht} such that Hi≅H for all 1≤i≤t. An H-supermagic decomposition of G is a bijection f:V(G)∪E(G)→1,2,…,VG+EG such that ∑v∈V(Hi)f(v)+∑e∈E(Hi)f(e) is a constant k for each Hi in the decomposition T and fVG=1,2,…,VG. If G admits an H-supermagic decomposition, then G is called H-supermagic decomposable. In this paper, we give necessary and sufficient conditions for the existence of K1,n-1-supermagic decomposition of the complete bipartite graph Kn,n minus a one-factor.


---

## Body

## 1. Introduction

All graphs in this paper are finite and simple. We use terminologies of graphs from West’s textbook [1]. If m and n are integers with m≤n, we denote {m,m+1,…,n} by [m,n].LetG be a graph. Acovering of G is a family of subgraphs H1,H2,…,Ht such that each edge of G belongs to at least one of the subgraphs Hi. If Hi≅H, for all i∈[1,t], then the covering is called an H-covering of G.Assume thatG has an H-covering. An H-magic labeling ofG is a bijection f:V(G)∪E(G)→1,VG+EG such that ∑v∈V(Hi)f(v)+∑e∈E(Hi)f(e) is a constant k for each Hi in the H-covering, and k is called amagic constant. An H-magic labeling f is called an H-supermagic labeling if f(V(G))=1,VG. A graph G is said to be H-supermagic if G admits an H-magic labeling.TheH-supermagic labeling was first introduced by Gutiérrez and Lladó [2] in 2005. They proved that many classes of graphs are H-supermagic, such as the complete bipartite graphs Km,n and the star K1,n are K1,l-supermagic for some positive integer l. In 2007, Lladó and Moragas [3] studied some windmills, wheels, and thetas which are H-supermagic. For example, they showed that the wheel Wn for odd n is C3-supermagic.In 2010, Ngurah et al. [4] proved that the fan Pn∨K1, the triangle ladder TLn, and K1,n∨K1 are C3-supermagic. Furthermore, they showed that the book Bn, the ladder Ln, and the grid Pm×Pn are C4-supermagic.AnH-decomposition of a graphG is an H-covering of G which forms a partition of the edge set of G. If G has an H-decomposition, then G is called H-decomposable. Assume that G is H-decomposable. If G admits an H-supermagic labeling, then G is said to be H-supermagic decomposable or G has an H-supermagic decomposition.The concept of anH-supermagic decomposition of G arises from the combination between graph labelings and graph decompositions which was introduced by Liang [5] in 2012. He found the conditions for the existence of C2k-supermagic decomposition of the complete n-partite graph as well as of multiple copies of it. Moreover, in 2015, Marimuthu and Kumar [6] showed that the complete bipartite graph Kn,n is K1,n-supermagic decomposable. For more information about graph labelings, please see Gallian’s survey [7].Motivated by the results of these authors, we are going to find necessary and sufficient conditions for the existence of anH-supermagic decomposition of the complete bipartite graph Kn,n minus a one-factor, where H≅K1,n-1. Hereafter, if H≅K1,n, for some positive integer n, then H is called an n-star subgraph. The notation of an n-star-subgraph was introduced by Akiyama and Kano [8].


## 2. Main Result

In this section, we consider the graphKn,n-I, where I is a one-factor of Kn,n and n≥2. Note that Kn,n-I is (n-1)-star-decomposable for all n≥2. Since VKn,n-I=2n and EKn,n-I=n2-n, we have VKn,n-I+EKn,n-I=n2+n.Theorem 1.
Letn be a positive integer with n≡2(mod4). Then Kn,n-I is not an (n-1)-star-supermagic decomposable graph.Proof.
Suppose thatKn,n-I is (n-1)-star-supermagic decomposable. Let f be an (n-1)-star-supermagic labeling of Kn,n-I with the magic constant k. Let U={u1,u2,…,un} and V={v1,v2,…,vn} be vertex-bipartitions of Kn,n-I. Let {H1,H2,…,Hn} be an (n-1)-star-decomposition of Kn,n-I, where Hi contains one vertex of U and n-1 vertices of V for all i∈1,2n.
Consider the labelingf; assume that all vertices of U are labeled by {a1,a2,…,an} and all vertices of V are labeled by {an+1,an+2,…,a2n}. Note that ai∈[1,2n] for all i∈[1,2n]. Then (1)∑i=1n∑v∈VHifv+∑i=1n∑e∈EHife=a1+a2+⋯+an+n-1an+1+an+2+⋯+a2n+2n+1+2n+2+⋯+n2+n=a1+a2+⋯+a2n+n-2an+1+an+2+⋯+a2n+∑i=2n+1n2+ni=∑i=12ni+n-2an+1+an+2+⋯+a2n+∑i=2n+1n2+ni=∑i=1n2+ni+n-2an+1+an+2+⋯+a2n=n2+nn2+n+12+n-2an+1+an+2+⋯+a2n.
Sincen≡2(mod4), we have 2∣n but 4∤n; that is, n=2(2k+1) for some integer k. Note that (n2+n)(n2+n+1)/2 is odd and (n-2)(an+1+an+2+⋯+a2n) is even. Thus, ∑i=1n∑v∈V(Hi)f(v)+∑i=1n∑e∈E(Hi)f(e) is odd. We know that ∑i=1n∑v∈V(Hi)f(v)+∑i=1n∑e∈E(Hi)f(e)=kn because the magic constant is k. Since n is even, this is impossible and results in a contradiction to our assumption. Hence, Kn,n-I is not an (n-1)-star-supermagic decomposable graph.The necessary condition for the existence of an(n-1)-star-supermagic decomposition of Kn,n-I is settled directly from Theorem 1.Corollary 2.
IfKn,n-I is (n-1)-star-supermagic decomposable, then n is odd or n≡0(mod4).Next we establish a structural lemma which will be used in the proof of Theorem4.Lemma 3.
For any positive integerm, the set 1,12m can be partitioned into 3 elements subsets which satisfy two conditions as follows:(i)
There are3m subsets of [1,12m] such that the summation of all elements in each subset is 18m+1.(ii)
There arem subsets of [1,12m] such that the summation of all elements in each subset is 18m+3.Proof.
Form∈N, let A=1,4m, let B=4m+1,8m, and let C=8m+1,12m.
Definef:A→B by (2)fi=8m-2i+1,ifi∈1,2m,6m,ifi=2m+1,12m-2i+4,ifi∈2m+2,3m+1,12m-2i+2,ifi∈3m+2,4m.
Letsi=i+f(i) for all i∈[1,4m]. Then the set (3)S=si∣i∈1,4m=6m+1,9m∪9m+3,10m+2.
Now, lets1′=6m+1, let s2′=6m+2,…, and let s3m′=9m and let s3m+1′=9m+3, let s3m+2′=9m+4,…, and let s4m′=10m+2. Thus, S=si′∣i∈1,4m.
Letci=12m-(i-1) for all i∈[1,4m]. Then C=8m+1,12m=ci∣i∈1,4m.
Defineg:S→C by g(si′)=ci for all i∈[1,4m]. For each i∈[1,4m], there exists an element sj∈S such that sj=si′, so g(sj)=g(si′)=ci. Then we have (4)j+fj+ci=18m+1,ifi∈1,3m,18m+3,ifi∈3m+1,4m.
Hence, there are3m subsets of [1,12m] such that the summation of all elements in each subset is 18m+1, and there are m subsets of [1,12m] such that the summation of all elements in each subset is 18m+3.Theorem 4.
Letn be a positive integer with n≡0(mod4). Then Kn,n-I is an (n-1)-star-supermagic decomposable graph with the magic constant (2n3+8n2-3n)/4.Proof.
Letn=4m for some positive integer m, and let U={u1,u2,…,un} and V={v1,v2,…,vn} be vertex-bipartition of Kn,n-I. Let {G1,G2,…,Gn} be an (n-1)-star-decomposition of Kn,n-I, where Gi≅K1,n-1 with V(Gi)={ui,v1,v2,…,vn}∖{vi} and E(Gi)={uiv1,uiv2,…,uivn}∖{uivi} for all i∈[1,n].
Define a total labelingf:V(Kn,n-I)∪E(Kn,n-I)→[1,n2+n] by(5)fui=2i,ifi∈1,3m,2i-1,ifi∈3m+1,4m,fvi=2i-1,ifi∈1,3m,2i,ifi∈3m+1,4m,for i∈[1,n], and (6)fuivj=2kn+i,ifi<j,j=2k,2kn+1-i,ifi<j,j=2k-1,2kn+i,ifi>j,j=2k-1,j≠n-3,2kn+2n+1-i,ifi>j,j=2k,j≠n-3,for i,j∈[1,n-3], where i≠j.
Note that(7)∑v∈VGifv=n2+n4+1,ifi∈1,3m,n2+n4-1,ifi∈3m+1,4m.
Now,n-4 edges of each Gi have been labeled with the partial magic sum (n3-4n2+n-4)/2, and their edges are labeled with values from [2n+1,n2-2n]. There are still three edges within each Gi which need to be labeled, and their label will come from [n2-2n+1,n2+n]. By applying Lemma 3 to the labeling f, we have the following properties: (i)
There are3m subsets of [n2-2n+1,n2+n] such that the summation of all elements in each subset is 3n2-3n/2+1.(ii)
There arem subsets of [n2-2n+1,n2+n] such that the summation of all elements in each subset is 3n2-3n/2+3.
Thus,Gi has the summation of its three remaining edges as 3n2-3n/2+1 for i∈[1,3m] and 3n2-3n/2+3 for i∈[3m+1,4m].
Hence, fori∈[1,3m],(8)∑v∈VHifv+∑e∈EHife=n2+n4+1+n3-4n2+n-42+3n2-3n2+1=2n3+8n2-3n4,and, for i∈[3m+1,4m],(9)∑v∈VHifv+∑e∈EHife=n2+n4-1+n3-4n2+n-42+3n2-3n2+3=2n3+8n2-3n4.
ThereforeKn,n-I is an (n-1)-star-supermagic decomposable graph, where n≡2(mod4) with the magic constant (2n3+8n2-3n)/4.Example 5.
Consider the graphK8,8-I. Let U={u1,u2,…,u8} and V={v1,v2,…,v8} be vertex-bipartition of K8,8-I. We have that K8,8-I is 7-star-supermagic decomposable by using the labeling f in Table 1 with the magic constant 378.Table 1
The 7-star-supermagic labelingf of K8,8-I.
(a)
i
1
2
3
4
5
6
7
8
f
(
u
i
)
2
4
6
8
10
12
13
15
f
(
v
i
)
1
3
5
7
9
11
14
16
(b)
f
(
u
i
v
j
)
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
u
1
—
17
32
33
48
52
57
72
u
2
18
—
31
34
47
51
59
71
u
3
19
30
—
35
46
50
61
70
u
4
20
29
36
—
45
49
63
69
u
5
21
28
37
44
—
53
60
68
u
6
22
27
38
43
56
—
58
67
u
7
23
26
39
42
55
62
—
66
u
8
24
25
40
41
54
64
65
—Theorem 6.
Letn be a positive integer, where n is odd and n≥3. Then Kn,n-I is an (n-1)-star-supermagic decomposable graph with the magic constant (n3+5n2-3n-1)/2.Proof.
LetU={u1,u2,…,un} and V={v1,v2,…,vn} be vertex-bipartition of Kn,n-I. Let {G1,G2,…,Gn} be an (n-1)-star-decomposition of Kn,n-I, where Gi≅K1,n-1 with V(Gi)={ui,v1,v2,…,vn}∖{vi} and E(Gi)={uiv1,uiv2,…,uivn}∖{uivi} for all i∈[1,n].
Define a total labelingf:V(Kn,n-I)∪E(Kn,n-I)→[1,n2+n] by (10)fui=i,fvi=n+i,for i∈[1,n], and (11)fuivj=2kn+i,ifi<j,j=2k,2kn+1-i,ifi<j,j=2k-1,2kn+i,ifi>j,j=2k-1,2kn+2n+1-i,ifi>j,j=2k,for i,j∈[1,n], where i≠j.
To get the magic constant from the labeling, we compute(12)∑v∈VHifv+∑e∈EHife=fui+∑j=1j≠infuj+∑j=1nfuivj=3n2-n2+n3+2n2-2n-12=n3+5n2-3n-12,for all i∈[1,n]. Hence Kn,n-I is an (n-1)-star-supermagic decomposable graph for all odd n.The following corollary is a direct consequence of Corollary2 and Theorems 4–6.Corollary 7.
Letn be a positive integer, where n≥2. Then Kn,n-I has an (n-1)-star-supermagic decomposition if and only if n is odd or n≡0(mod4).



---

*Source: 5104701-2017-06-21.xml*