# On Graceful Spider Graphs with at Most Four Legs of Lengths Greater than One

Authors: A. Panpa; T. Poomsa-ard
Journal: Journal of Applied Mathematics
 (2016)

---

## Abstract

A graceful labeling of a treeT with n edges is a bijection f:V(T)→{0,1,2,…,n} such that {|f(u)-f(v)|:uv∈E(T)} equal to {1,2,…,n}. A spider graph is a tree with at most one vertex of degree greater than 2. We show that all spider graphs with at most four legs of lengths greater than one admit graceful labeling.


---

## Body

## 1. Introduction

Labeled graphs form useful models for a wide range of disciplines and applications such as in coding theory, X-ray crystallography, radar, astronomy, circuit design, and communication network addressing [1]. A systematic presentation of diverse applications of graph labeling is presented in [2].A graceful labelingf of a tree T is a bijective function from the set of vertices V(T) of T to the set {0,1,2,…,|E(T)|} such that when each edge xy is assigned the label |f(x)-f(y)|, the resulting edge labels are distinct. A tree which admits graceful labeling is called a graceful tree. In 1964, Ringel and Rosa (see [3, 4]) gave the famous and unsolved “graceful tree conjecture” which stated that all trees are graceful.A spider graph is a tree with at most one vertex of degree greater than 2. Gallian [1] has noted that the special case of this conjecture regarding spider graphs is still open and that very few classes of spider graphs are known to be graceful. Huang et al. [5] proved that all spider graphs with three or four legs are graceful. Bahls et al. [6] also proved that every spider graph in which the lengths of any two of its legs differ by at most one is graceful. Jampachon et al. [7] have also proven that Sn(k,l,m) is graceful, if n is large enough, where Sn(k,l,m) is defined in Section 3.In this paper, we prove that all spider graphs with at most four legs of lengths greater than one are graceful.


## 2. Preliminaries

LetT be a tree with n edges. Agraceful labeling of T is a bijection f:V(T)→{0,1,2,…,n} such that when each edge xy is assigned the label |f(u)-f(v)|, the edge label set is equal to {1,2,…,n}. A tree which admits graceful labeling is called agraceful tree.To prove our results, we need some terminology and existence results which are described below. In [8], Hrnčiar and Haviar proved Lemma 1 and in [9] Jampachon and Poomsa-Ard proved Lemmas 2 and 3.Lemma 1.
LetT be a tree with n edges and a graceful labeling f. Then, the function f∗:V(T)→{0,1,2,…,n} defined by f∗(v)=n-f(v) is also a graceful labeling of T.Lemma 2.
LetP2n be a path graph with V(P2n)={v1,v2,v3,…,v2n} and let M={a+1,a+2,…,a+n,m+a+1,m+a+2,…,m+a+n}, m≥n and a≥0. Then, there is a bijective labeling f′:V(P2n)→M such that f′(v1)=i or f′(v2n)=i, where i∈M and the edge label set is {m-n+1,m-n+2,…,m+n-1}.Lemma 3.
LetPn, n≥4, be a path graph with V(Pn)={v1,v2,v3,…,vn} and let M={m,m+1,m+2,…,m+n-1}. Then, there is a bijective labeling f′:V(Pn)→M such that f′(v1)=i or f′(vn)=i, where i∈M and the edge label set is {1,2,3,…,n-1}.LetT be a tree and let u be a leaf of T. Let T(u,u1,u2,…,un) be the tree obtained from T by adding the vertices u1,u2,…,un and the edges uu1,u1u2,…,un-1un. In [10], Sangsura and Poomsa-Ard have proved Lemma 4.Lemma 4.
If a treeT has a graceful labeling f such that f(u)=0, where u is a leaf of T, then T(u,u1,u2,…,un) is graceful for each n≥1.


## 3. Main Results

Aspider graph orspider is a tree with at most one vertex of degree greater than 2 and this vertex is called thebranch vertex and is denoted by v0. Aleg of a spider graph is a path from the branch vertex to a leaf of the tree. Let Sn(m1,m2,…,mk), n≥k, denote a spider of n legs such that its legs has length one except for k legs of lengths m1,m2,…,mk, where mi≥2 for all i=1,2,…,k.Lemma 5.
IfSk(m1,m2,…,mk) has a graceful labeling f such thatf(v0)=0, then there is a graceful labeling f′ of Sn(m1,m2,…,mk) such that f′(v0)=0.Proof.
LetT=Sn(m1,m2,…,mk) be a graph such as shown in Figure 1(a). Since f is a graceful labeling of a subgraph Sk(m1,m2,…,mk) of T, extending f to T such that fui=i+m1+m2+⋯+mk, i=1,2,…,n-k, then we get that f is a graceful labeling of T as shown in Figure 1(b).Figure 1 (a) (b)Theorem 6.
The graphSn(m) is graceful.Proof.
We note thatS1(m) is a path of length m; for example, S1(m)=v0,v1,…,vm. Let f be a labeling of S1(m) by labels alternating between the lowest and highest unused numbers in the set {0,1,2,…,m}. We have that f is a graceful labeling of S1(m) such that f(v0)=0 and by Lemma 5 we get that Sn(m) is graceful.Lemma 7.
IfSk(m1,m2,…,mk) has a graceful labeling f such thatf(v0)=0, then Sn(l,m1,m2,…,mk) is also graceful.Proof.
By assumption and Lemma5, there exists a graceful labeling f′ of Sn(m1,…,mk) such that f′(v0)=0. From the proof of Lemma 5, we see that f′(un-k) is the maximum number; that is, f′un-k=n-k+m1+m2+⋯+mk. Let f∗(v)=(n-k)+m1+m2+⋯+mk-f′(v) for all vertices of Sn(m1,…,mk). By Lemma 1, we get that the function f∗ is a graceful labeling of Sn(m1,…,mk) such that f∗(un-k)=0. Then, Sn(l,m1,m2,…,mk) is graceful by Lemma 4.Theorem 8.
The graphSn(l,m) is graceful.Proof.
From the proof of Theorem6, we see that the labeling f of S1(m) is a graceful labeling such that f(v0)=0. By Lemma 7, we therefore get that Sn(l,m) is also graceful.Theorem 9.
The graphSn(l,m,p) is graceful.Proof.
Without loss of generality, letm≤p and let P be the path as shown in Figure 2.
Letf be a labeling of P by labels alternately between the lowest and highest unused numbers in the set {0,1,2,…,m+p}. We have that f is a graceful labeling of P such that f(v0)=0. Note that S2(m,p)≠P and |f(vm)-f(vm+1)|=p. Since f(v2m)=p if m=p and f(v2m+1)=p if m<p, then by Lemma 3 we can find a graceful labeling f′ of S2(m,p) such that f′(v0)=0. Hence, Sn(l,m,p) is graceful by Lemma 7.Figure 2Theorem9 is not a new result; it follows from Jampachon and Poomsa-Ard [9], but our proof here is shorter.Next, consider the pathP obtained from S3(m,p,q) by deleting the edges v0vm+1 and v0vm+p+1 and adding the edges vmvm+1 and vm+pvm+p+1 as shown in Figure 3.Figure 3It can be seen that|V(P)|=m+p+q+1 and |E(P)|=m+p+q. If we now introduce a special labeling f of P which can be used to generate a graceful labeling, it follows thatf(vi)=i/2 if i is even, and f(vi)=m+p+q-(i-1)/2 if i is odd.It can be seen that with the labeling above the labels alternate between the lowest and highest unused numbers in the set {0,1,2,…,m+p+q}. Moreover, we see that P admits graceful labeling and that the label of the branch vertex is 0; that is, f(v0)=0. For convenience, we call the labeling above Type∗.Remark 10.
LetP be the path obtained from T=S3(m,p,q) as shown in Figure 3 and let f be the labeling of P of Type∗. Note that S3(m,p,q)≠P, |f(vm)-f(vm+1)|=f(v2m+1)=p+q, and |f(vm+p)-f(vm+p+1)|=q. To find a graceful labeling f′ of T, we change the values of f at the vertices vm+1 and vm+p+1 of P such that f′(vm+1)=p+q and f′(vm+p+1)=q.Next we want to show thatSn(l,m,p,q) are graceful and to prove this result we need the following lemmas.Lemma 11.
Ifm=p=q, then there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.Proof.
LetP be the path as shown in Figure 4 and let f be the labeling of P of Type∗. We see that |f(vm)-f(vm+1)|=f(v2m+1)=p+q=2m and |f(v2m)-f(v2m+1)|=f(v2m)=q=m, where v2m is the leaf of the path vm+1,…,v2m. If we change the values of f at vm+1,…,v2m by reversing their labels, then we get a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.Figure 4Lemma 12.
Ifm=p<q and q=2m+1, then there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.Proof.
LetP be the path as shown in Figure 5 and let f be the labeling of P of Type∗. We see that |f(vm)-f(vm+1)|=f(v2m+1)=p+q and |f(v2m)-f(v2m+1)|=f(v4m+1)=q.
To construct a graceful labelingf′ of T=S3(m,p,q), we consider two cases.
Case  1 ( m is odd). First, we switch the values of f at vi and vi+1, i=m+1,m+3,m+5,…,4m, such that the new value of f at v2m is p+q and at v4m is q. We then change the new values of f at vm+1,vm+2,…,v2m by reversing their labels; then, by Lemma 3, we can find a graceful labeling f′ of T such that f′(v0)=0.
Case  2 ( m is even). Define f′ as follows: for 0≤i≤m, f′(vi)=f(vi) such thatform+1≤i≤3m/2,
f′(vi)=(m+i)/2 if i is evenf′(vi)=7m/2-(i-3)/2 if i is odd,for3m/2+1≤i≤2m,
f′(vi)=i/2 if i is evenf′(vi)=4m-(i-3)/2 if i is odd,for2m+1≤i≤5m/2+1,
f′(vi)=5m/2-(i-2)/2 if i is evenf′(vi)=3m/2+(i+1)/2 if i is odd,for5m/2+2≤i≤6m/2+1,
f′vi=(m+i)/2 if i is evenf′(vi)=7m/2-(i-3)/2 if i is oddfor6m/2+2≤i≤7m/2+1,
f′(vi)=i/2 if i is evenf′(vi)=4m-(i-3)/2 if i is odd,for7m/2+2≤i≤4m+1,
f′vi=5m/2-(i-2)/2 if i is evenf′(vi)=3m/2+(i+1)/2 if i is odd.
In accordance with the above labeling pattern, we get a graceful labelingf′ of T such that f′(v0)=0.Figure 5Lemma 13.
Ifm<p=q, then there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.Proof.
LetP be the path as shown in Figure 6 and let f be the labeling of P of Type∗. We see that |f(vm)-f(vm+1)|=f(v2m+1)=p+q=2p and |f(vm+p)-f(vm+p+1)|=f(v2p)=q=p.
Ifp is even, then by Lemmas 2 and 3, we can find a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0. Now suppose that p is odd. To construct a graceful labeling f′ of T=S3(m,p,q), we must consider two cases.
Case  1 ( m is even)
Case  1.1 ( p < 2 m + 1 ). We see that |f(v2m)-f(v2m+1)|=|f(vm+p)-f(v3m-p+1)| and v3m-p+1 lies in the path vm+1,…,v2m. Change the values of f at vm+1,vm+2,…,vm+p by reversing their labels; then, the new value of f at vp is 2p. Next, change the new values of f at vm+1,vm+2,…,vp by reversing their labels. Since the number of vertices of the path vp+1,vp+2,…,vp+m is even, by Lemmas 2 and 3, we can find a graceful labeling f′ of T such that f′(v0)=0.
Case  1.2 ( p = 2 m + 1 ). Define f′ as follows: For 0≤i≤m, f′(vi)=f(vi) andform+1≤i≤2m+1,
f′(vi)=3m/2-(i-2)/2 if i is evenf′(vi)=7m/2+(i+3)/2 if i is odd,for2m+2≤i≤2m+p+1,
f′(vi)=(m+i)/2 if i is evenf′(vi)=9m/2-(i-5)/2 if i is odd,for2m+p+2≤i≤m+2p,
f′(vi)=7m/2-(i-4)/2 if i is evenf′(vi)=3m/2+(i+1)/2 if i is odd.
In accordance with the above labeling pattern, we get a graceful labelingf′ of T such that f′(v0)=0.
Case  1.3 ( p > 2 m + 1 ). We see that |f(v2m+1)-f(v2m+2)|=|f(vm+1)-f(v3m+2)| and v3m+2 lies in the path v2m+2,…,vm+p. Change the values of f at vm+1,vm+2,…,v2m+1 by reversing their labels. Since the number of vertices of the path v2m+2,v2m+3,…,vm+p is even, by Lemmas 2 and 3, we can find a graceful labeling f′ of T such that f′(v0)=0.
Case  2 ( m is odd). Switch the values of f at vi and vi+1, i=m+1,m+3,m+5,…,m+2p-1; after that, follow a similar procedure as for Case  1.Figure 6Lemma 14.
Ifm<p<q and p≠2m+1, then there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.Proof.
LetP be the path as shown in Figure 3 and let f be the labeling of P of Type∗. We see that f(v2m+1)=p+q and, since p<q, there must be a vertex vj laying in the path Pq=vm+p+1,…,vm+p+q such that f(vj)=q. If p is even, then by Lemmas 2 and 3, we can find a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0. Now suppose that p is odd.
Case  1 ( m is even)
Case  1.1 ( p < 2 m + 1 ). Do similarly as in Case  1.1 of Lemma 13.
Case  1.2 ( p > 2 m + 1 ). Do similarly as in Case  1.3 of Lemma 13.
Case  2 ( m is odd). Switch the values of f at vi and vi+1, i=m+1,m+3,m+5,…,m+2p-1, after which do similarly as in Case  1.Theorem 15.
Letl, m, p, and q be integers greater than one. Then, there are three of them; say x, y, and z, for which the spider graph S3(x,y,z) has a graceful labeling f such that f(v0)=0.Proof.
Without loss of generality, letm≤p≤q, let P be the path as shown in Figure 5, and let f be the labeling of P of Type∗.
Case  1 ( m = p = q ). By Lemma 11 there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.
Case  2 ( m = p < q ). If q=2m+1, then by Lemma 12 there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0. Now suppose that q≠2m+1.
Ifl<m, then by Lemma 13 there is a graceful labeling f′ of S3(l,m,p) such that f′(v0)=0.
Ifl=m, then by Lemma 11 there is a graceful labeling f′ of S3(l,m,p) such that f′(v0)=0.
Ifm<l<q and l=2m+1, then by Lemma 12 there is a graceful labeling f′ of S3(m,p,l) such that f′(v0)=0.
Ifm<l<q and l≠2m+1, then by Lemma 14 there is a graceful labeling f′ of S3(m,l,q) such that f′(v0)=0.
Ifl=q, then by Lemma 13 there is a graceful labeling f′ of S3(m,l,q) such that f′(v0)=0.
Ifl>q and l=2m+1, then by Lemma 12 there is a graceful labeling f′ of S3(m,p,l) such that f′(v0)=0.
Ifl>q and l≠2m+1, then by Lemma 14 there is a graceful labeling f′ of S3(m,q,l) such that f′(v0)=0.
Case  3 ( m < p = q ). By Lemma 13 there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0.
Case  4 ( m < p < q ). If p≠2m+1, then by Lemma 14 there is a graceful labeling f′ of S3(m,p,q) such that f′(v0)=0. Now suppose that p=2m+1.
Ifl<m, then by Lemma 14 there is a graceful labeling f′ of S3(l,p,q) such that f′(v0)=0.
Ifl=m, then by Lemma 12 there is a graceful labeling f′ of S3(l,m,p) such that f′(v0)=0.
Ifm<l<p, then by Lemma 14 there is a graceful labeling f′ of S3(l,p,q) such that f′(v0)=0.
Ifl=p, then by Lemma 13 there is a graceful labeling f′ of S3(m,l,p) such that f′(v0)=0.
Ifp<l<q, then by Lemma 14 there is a graceful labeling f′ of S3(m,l,q) such that f′(v0)=0.
Ifl=q, then by Lemma 13 there is a graceful labeling f′ of S3(m,l,q) such that f′(v0)=0.
Ifl>q, then by Lemma 14 there is a graceful labeling f′ of S3(m,q,l) such that f′(v0)=0.Theorem 16.
The graphSn(l,m,p,q) is graceful.Proof.
By Theorem15, there is a graceful labeling f of a spider graph S3(m,p,q) with three legs, such that f(v0)=0. By Lemma 7, we therefore get that Sn(l,m,p,q) is graceful.


## 4. Conclusion and Remarks

The main tools required to construct a graceful labeling ofSn(l,m,p,q) are a graceful labeling f with f(v0)=0, where v0 is the branch vertex, and the results of Lemmas 2 and 3.



---

*Source: 5327026-2016-11-23.xml*