# Edgeδ− Graceful Labeling for Some Cyclic-Related Graphs

Authors: Mohamed R. Zeen El Deen
Journal: Advances in Mathematical Physics
 (2020)

---

## Abstract

In this paper, we introduce a new type of labeling of a graphG with p vertices and q edges called edge δ− graceful labeling, for any positive integer δ, as a bijective mapping f of the edge set EG into the set δ,2δ,3δ,⋯,qδ such that the induced mapping f∗:VG→0,δ,2δ,3δ,⋯,qδ−δ, given by f∗u=∑uv∈EGfuvmodδk, where k=maxp,q, is an injective function. We prove the existence of an edge δ− graceful labeling, for any positive integer δ, for some cycle-related graphs like the wheel graph, alternate triangular cycle, double wheel graph Wn,n, the prism graph Πn, the prism of the wheel PWn, the gear graph Gn, the closed helm CHn, the butterfly graph Bn, and the friendship Frn.


---

## Body

## 1. Introduction

The graphs considered here will be finite, undirected, and simple whereVG and EG will denote the vertex set and edge set of a graph G, respectively, p=VG and q=EG.A labeling of a graph is a mapping that carries graph elements (edges or vertices, or both) to positive integers, subject to certain constraints. A labeling of a graph is called edge labeling if the domain of the mapping is the edge set. Graph labeling methods are used for application problems in a communication network addressing system, for fasting communication in sensor networks, and for designing fault-tolerant systems with facility graphs, in coding theory for the design of good radar type codes, and can also be used for issues in mobile ad hoc networks [1–3].In the early 1960s, the idea of graph labelings was introduced by Rosa in [4]. Following this paper, different techniques have been studied in graph labelings. One such graph labeling technique is the edge graceful labeling introduced by Lo [5]. In 1985 as a bijective, f from the set of edges to the set 1,2,⋯,q such that the induced map f∗ from VG to 0,1,2,⋯,p−1 given by f∗u=∑uv∈EGfuvmodp is a bijective. The graph that admits a graceful labeling is called a graceful graph.Solairaju and Chithra [6] in 2009 introduced a labeling of G called edge odd graceful labeling, which is a bijection f from the set of edges EG to the set 1,3,⋯,2q−1 such that the induced map f∗ from VG to 0,1,2,⋯,2q−1 given by f∗u=∑uv∈EGfuvmod2q is an injective. For many results on this type of labeling, see [7–10].Recently, a new type of labeling is introduced by Elsonbaty and Daoud [11] called edge even graceful labeling, which is a bijective f from the set of edges EG to the set 2,4,⋯,2q such that the induced map f∗ from VG to 0,2,4,⋯,2k−2 given by f∗u=∑uv∈EGfuvmod2k where k=maxp,q is an injective. Several results have been published on edge even graceful labeling, see [12–15]. For a detailed survey on graph labeling, refer to a dynamic survey of graph labeling [16].Now, we introduce a generalization of the edge graceful labeling to edgeδ− graceful labeling for any positive integer δ.Definition 1.
An edgeδ− graceful labeling of a graph G=VG,EG, with p=VG vertices and q=EG edges, for any positive integer δ, is a bijective mapping f of the edge set EG into the set δ,2δ,3δ,⋯,qδ such that the induced mapping f∗:VG→0,δ,2δ,3δ,⋯,qδ−δ, given by f∗u=∑uv∈EGfuvmodδk, where k=maxp,q, is an injective function. The graph that admits an edge δ− graceful labeling is called an edge δ− graceful graph.
Note that, ifδ=2, we have the edge even labeling; also, if δ=3, we have the edge triple labeling and so on. The odd cycle Cn whose vertices v1,v2,⋯,vn and edges (vivi+1) where i=1,2,⋯,n is an edge δ− graceful graph if and only if n is odd. Labeling the edges, respectively, by δ,2δ,3δ,⋯,nδ yields the labels δ,3δ,5δ,⋯,0;2δ,4δ,⋯,n−1δ on vertices, respectively. In Figure 1, we present an edge 5− graceful labeling of a graph and an edge 4− graceful labeling of another graph.Figure 1
A graph with edge 5− graceful labeling and an edge 4− graceful labeling of another graph.


## 2. Edgeδ− Graceful Labeling of the Wheel Graph Wn

Theorem 2.
For any positive integerδ, the wheel graph Wn, n>3 is an edge δ− graceful graph.Proof.
Letv0,v1,v2,⋯,vn be the vertices of Wn with hub vertex v0, and the edges of Wn will be v0vi,vivi+1,i=1,2,⋯,n. So, pVWn=n+1 and q=EWn=2n. There are three cases:Case 1.
n≡0mod4, or n≡1mod4.
We define the labeling functionf:EWn→δ,2δ,3δ,⋯,2nδ as follows:
(1)fv0vi=iδ,fori∈1,2,3,⋯,n−1,fv1vn=n+1δ,fvivi+1=δ2n−i+1,fori∈1,2,3,⋯,n−1.
Then, the induced vertex labels are(2)f∗v1=δn+2,f∗vi=δ2n−i+3mod2nδ,i=2,⋯,n.
Hence, the labels of the verticesv2,v3,v4,⋯,vn−1,vn will be δ,0,δ2n−1,⋯,δn+4,δn+3, respectively, which are all a multiple of δ and distinct numbers.
(3)f∗v0=∑i=1nfv0vimod2nδ=∑i=1nδimod2nδ=δ2n2+nmod2nδ.
(i)
Ifn≡0mod4⇒n=4r⇒δq=2nδ=8rδ, then
(4)f∗v0=8r2δ+2rδmod8rδ≡2rδmod8rδ=nδ2
(ii)
Ifn≡1mod4, then f∗v0=nδCase 2.
n≡2mod4. Define the labeling function f as follows:
(5)fv1vn=nδ,fvivi+1=iδ,fori∈1,2,3,⋯,n−1,fv0v1=n+1δ,fv0vi=δ2n−i+2,fori∈1,2,3,⋯,n−1.
Then, the induced vertex labels aref∗v1=2δ and f∗vi=δi+1mod2nδ,i∈2,3,⋯,n. Hence, the labels of the vertices v2,v3,⋯,vn−1,vn will be 3δ,4δ,⋯,δn,δn+1, respectively.
(6)f∗v0=∑i=1nfv0vimod2nδ=∑i=1nnδ+iδmod2nδ=δ23n2+nmod2nδ.
(i)
Ifn≡2mod4⇒n=4r+2⇒δq=2nδ=8rδ+4δ, then
(7)f∗v0=24r2δ+26rδ+7δmod8r+4δ≡6rδ+3δmod8rδ+4δ=3nδ2Case 3.
n≡3mod4. Define the labeling function f as follows:
(8)fv0v1=2δ,fv0vi=δn−i+3,fori∈2,3,⋯,n,fv1vn=δ,fvivi=1=δn+i,fori∈1,2,3,⋯,n−1.
Then, the induced vertex labels aref∗v1=3δ, f∗v2=4δ, and f∗vi=δn+i+2mod2nδ, i=3,4,⋯,n. Hence, the labels of the vertices v3,v4,⋯,vn−1,vn will be δn+5,δn+6,⋯,δ,2δ, respectively.
(9)f∗v0=∑i=2n+1fv0vimod2nδ=nδ+∑i=1niδmod2nδ=δ2n2+3nmod2nδ.
(i)
Ifn≡3mod4⇒n=4r+3⇒δq=2nδ=8rδ+6δ, then
(10)f∗v0=18r2δ+18rδ+9δmod8rδ+6δ≡4rδ+3δmod8rδ+6δ=nδ
It is clear that, in all cases, for alli∈1,2,3,⋯,n, the labels of the vertices vi are all distinct, multiple of δ, and different from f∗v0 which complete the proof.
It should be noted thatW3 is not an edge δ− graceful graph because for any bijective function f:EW3→δ,2δ,⋯,6δ, there is no injective induced function f∗ that satisfied the requirementsIllustration 1. In Figure 2, we present W13 with edge 5− graceful labeling, W16 with edge 3− graceful labeling, W14 with edge 4− graceful labeling, and W15 with edge 6− graceful labeling, respectively.Figure 2
W13 with edge 5− graceful labeling, W16 with edge 3− graceful labeling, W14 with edge 4− graceful labeling, and W15 with edge 6− graceful labeling.


## 3. Edgeδ− Graceful Labeling of the Alternate Triangular Cycle AC2n

Definition 3 (see [16]).
An alternate triangular cycleAC2n is obtained from an even cycle C2n=v1,u1,v2,u2,⋯,vn,un by joining vi and ui to a new vertex wi. That is, every alternate edge of a cycle is replaced by C3.Theorem 4.
For any positive integerδ, the alternate triangular cycle AC2n is an edge δ− graceful graph.Proof.
Let the alternate triangular cycleAC2n be given as in Figure 3 with the edge set will be viui,ui,vi+1,viwi,uiwi,i=1,2,⋯,n. The graph AC2n has p=3n and q=4n. We define the labeling function f:EAC2n→δ,2δ,3δ,⋯,4nδ by
(11)fviui=δi,fori∈1,2,3,⋯,n,funv1=3n+1δ,fuivi+1=4n−i+1δ,fori∈1,2,3,⋯,n−1,fv1w1=2n+2δ,fviwi=δn+1+i,fori∈2,3,⋯,n,fu1w1=n+2δ,funwn=n+1δ,fuiwi=δ2n+1+i,fori∈2,3,⋯,n−1.
By using the above labeling pattern, the induced vertex labels will be(12)f∗v1=δn+4,f∗vn=δ2n+3andfori=2,3,⋯,n−1,f∗vi=fviui+fviwi+fui−1vimod4nδ=δn+3+imod4nδ,f∗u1=δn+3,f∗un=δn+2andfori=2,3,⋯,n−1,f∗ui=fviui+fuiwi+fuivi+1mod4nδ=δ2n+2+imod4nδ,f∗w1=δ3n+4,f∗wn=δ3n+2,f∗wi=δ3n+2+2imod4nδ,i=2,3,⋯,n−1.
Hence, the labels of the verticesv2,v3,⋯,vn−1 will be δn+5,δn+6,⋯,δ2n+2, respectively, the labels of the vertices u2,u3,⋯,un−1,un will be δ2n+4,δ2n+5,⋯,δ3n+1, respectively, and the labels of the vertices w2,w3,⋯,wn−1 will be δ3n+6,δ3n+8,⋯,δn, respectively. Hence, there are no repeated vertex labels which complete the proof.Illustration 2. In Figure 4, we present an alternate triangular cycle AC16 with an edge 4− graceful labeling.Figure 3
An alternate triangular cycleAC2n with edge ordinary labeling.Figure 4
An alternate triangular cycleAC16 with an edge 4− graceful labeling.


## 4. Edgeδ− Graceful Labeling of the Double Wheel Graph Wn,n

Theorem 5.
For any positive integerδ, the double wheel graph Wn,n is an edge δ− graceful graph.Proof.
The double wheel graphWn,n consists of two cycles of n vertices connected to common hub. Let v1,v2,⋯,vn be the vertices of one wheel and u1,u2,⋯,un be the vertices of other wheel with hub vertex v0; the edges of Wn,n will be v0vi,vivi+1,v0ui,uiui+1,i=1,2,⋯,n. So, p=VWn,n=2n+1 and q=EWn,n=4n, see Figure 5. There are two cases:Case 1.
Whenn is even. We define the labeling function f:EWn,n→δ,2δ,3δ,⋯,4nδ as follows:
(13)fv0vi=2n+iδ,fv0ui=3n+iδ,fori∈1,2,3,⋯,n,fv1vn=nδ,fvivi+1=iδ,fori∈1,2,3,⋯,n−1,fu1un=2nδ,fuiui+1=n+iδ,fori∈1,2,3,⋯,n−1.
Then, the induced vertex labels are(14)f∗v1=δ3n+2,f∗vi=δ2n+3i−1mod2nδ,i=2,⋯,n,f∗u1=δ2n+2,f∗ui=δn+3i−1mod4nδ,i=2,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn are δ2n+5,δ2n+8,⋯,δn−4,δn−1, respectively, and the labels of the vertices u2,u3,⋯,un−1,un are δn+5,δn+8,⋯,δ4n−4,δ4n−1, respectively.
(15)f∗v0=∑i=1nfv0vi+fv0vimod4nδ=∑i=1n2iδ+5nδmod4nδ=5n2δ+nn+1δmod4nδ=δ6n2+nmod4nδ.
Sincen≡0mod2⇒n=2r⇒δq=4nδ=8rδ, then
(16)f∗v0=24r2δ+2rδmod8rδ≡2rδmod8rδ=nδ.Case 2.
Ifn is odd number, define the labeling function f as follows:
(17)fv0vi=iδ,fv0ui=n+iδ,fori∈1,2,3,⋯,n,fv1vn=2n+1δ,fvivi+1=3n−i+1δ,fori∈1,2,3,⋯,n−1,fu1un=3n+1δ,fuiui+1=4n−i+1δ,fori∈1,2,3,⋯,n−1.
Then, the induced vertex labels are(18)f∗v1=δn+2,f∗vi=δ2n−i+3mod4nδ,i=2,⋯,n,f∗u1=2δ,f∗ui=δn−i+3mod4nδ,i=2,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn−1,vn will be δ2n+1,δ2n,⋯,δn+4,δn+3, respectively, and the labels of the vertices u2,u3,⋯,un−1,un are n+1δ,nδ,⋯,4δ,3δ, respectively.
(19)f∗v0=∑i=1nfv0vi+fv0vimod4nδ=∑i=1niδ+n+iδmod4nδ=n2δ+nn+1δmod4nδ=δ2n2+nmod4nδ.
Clearly, the vertex labels are all distinct, multiple ofδ, and different from f∗v0. Thus, the double wheel graph is an edge δ− graceful graph for any positive integer δ.Illustration 3. In Figure 6, we present W9,9 with edge 4− graceful labeling and W10,10 with edge 5− graceful labeling.Figure 5
The double wheel graphWn,n with ordinary labeling.Figure 6
The graphsW9,9 with edge 4− graceful labeling and W10,10 with edge 5− graceful labeling.


## 5. Edgeδ− Graceful Labeling of the Prism Graph Πn

Theorem 6.
For any positive integerδ, the prism graph Πn is an edge δ− graceful graph.Proof.
Letv0,v1,v2,⋯,vn be the vertices of Cn and Cn′=u0,u1,u2,⋯,un be a copy of Cn. The prism Πn is defined by joining each vi of Cn to the corresponding vertex ui of Cn′ for all i∈1,2,3,⋯,n; edges of Wn will be vivi+1,viui,uiui+1,i=1,2,⋯,n. Thus, an n-prism graph has p=2n vertices and q=3n edges.
Let the vertex and edge symbols be given as in Figure7.
Define the labeling mappingf:EΠn→δ,2δ,3δ,⋯,3nδ by
(20)fv1vn=nδ,fvivi+1=iδ,fori∈1,2,3,⋯,n−1,fu1un=3nδ,fuiui+1=δ2n+i,fori∈1,2,3,⋯,n−1,fv1u1=δn+1,fviui=δ2n+2−i,fori∈2,3,⋯,n.
So the induced vertex labels will be(21)f∗v1=δ2n+2,f∗vi=δ2n+1+imod3nδ,fori∈2,3,⋯,n,f∗u1=2δ,f∗ui=δi+1,fori∈2,3,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn−1,vn will be δ2n+3,δ2n+4,⋯,0,δ, respectively, and the labels of the vertices u2,u3,⋯,un−1,un will be 3δ,4δ,⋯,δn,δn+1, respectively.
Overall, the labels of the vertices are all different and multiplies ofδ. Thus, the prism graph Πn is an edge δ− graceful graph for any positive integer δ.Illustration 4. In Figure 8, we present Π10 with edge 7− graceful labeling.Figure 7
The prism graphΠn with ordinary labeling.Figure 8
TheΠ10 with edge 7− graceful labeling.


## 6. Edgeδ− Graceful Labeling of the Prism of the Wheel PWn

Definition 7 (see [3]).
Forn≥3, let v0,v1,v2,⋯,vn be the vertices of Wn with hub vertex v0 and Wn′=u0,u1,u2,⋯,unbe a copy of Wn. Define PrismWn, called the prism of Wn, by PWn=K2×Wn, i.e., joining v0 of Wn to the corresponding vertex u0 of Wn′ and each vi of Wn to the corresponding vertex ui of Wn′ for all i∈1,2,3,⋯,n. Thus, EPWn=EWn∪EWn′∪viuii∈1,2,3,⋯,n∪v0u0.Theorem 8.
For any positive integerδ, the prism of the wheel PWn is an edge δ− graceful graph, when n is even.Proof.
The prism of the wheelPWn has p=2n+2 vertices and q=5n+1 edges, the edges will be v0vi,vivi+1,u0ui,uiui+1,viui,v0ui,i=1,2,⋯,n. Let the vertex and edge symbols be given as in Figure 9.
We define the labeling functionf:EPWn→δ,2δ,3δ,⋯,5n+1δ by
(22)fv0u0=δ5n+1,fviui=δifori∈1,2,3,⋯,n,fv1vn=δn+1,fvivi+1=δ2n−i+1fori∈1,2,3,⋯,n−1,fv0v1=δ2n+1,fv0vi=δ3n−i+2fori∈2,3,⋯,n,fu1un=δ3n+1,fuiui+1=δ4n−i+1fori∈1,2,3,⋯,n−1,fu0u1=δ4n+1,fu0ui=δ5n−i+2fori∈2,3,⋯,n.
In view of the above labeling pattern, then the induced vertex labels are(23)f∗v1=2δ,f∗vi=δ2n−2i+4mod5n+1δ,i=2,3,⋯,n,f∗u1=n+1δ,f∗ui=δ3n−2i+3mod5n+1δ,i=2,3,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn−1,vn are 2nδ,2n−2δ,⋯,6δ,4δ, respectively, and the labels of the vertices u2,u3,⋯,un−1,un are 3n−1δ,3n−3δ,⋯,n+5δ,n+3δ, respectively.
Hence, there are no repeated vertex labels. Also in this labeling, we can check that(i)
fv0v1+fv0v2mod5n+1δ=0
(ii)
fv0v1+fv0vn−i+3mod5n+1δ=0,i=3,4,⋯,n/2+1
Then,f∗v0=∑i=1nfv0vi+fv0u0mod5n+1δ=0, finally
(24)f∗u0=∑i=1nfu0ui+fv0u0mod5n+1δ=δ29n2+nmod5n+1δ.
There are three cases:Case 1.
Whenn≡0mod10 or n≡2mod10 or n≡8mod10.
(i)
Ifn≡0mod10⇒n=10r⇒δq=5n+1δ=50r+1δ, then f∗u0=450r2δ+5rδmod50r+1δ≡46rδ+δmod50r+1δ=23n+5/5δ
(ii)
Ifn≡2mod10, then f∗u0=18n+4/5δ
(iii)
Ifn≡8mod10, then f∗u0=3n+1/5δCase 2.
Whenn≡4mod10,⇒n=10r+4⇒δq=5n+1δ=50r+21δ, then
(25)f∗u0=450r2δ+365rδ+74δmod50r+21δ≡26rδ+11δmod50r+21δ=13n+35δ.
In this case, we havef∗u0 will equal to f∗ui when i=n+6/5, so we change the labeling of two edges (u0v0) and (u0un+6/5) as follows: fu0v0=24n+4/5δ and fu0vn+6/5=δ5n+1.
Then,f∗v0=24n+4/5δ, and f∗un+6/5=14n+4/5δ.Case 3.
Whenn≡6mod10,⇒n=10r+6⇒δq=5n+1δ=50r+31δ, then
(26)f∗u0=450r2δ+545rδ+165δmod50r+31δ≡16rδ+10δmod50r+31δ=8n+25δ.
In this case, we havef∗u0 will equal to f∗vi when i=n+9/5, so we change the labeling of two edges (u0v0) and v0vn+9/5 as follows: fu0v0=14n+1/5δ and fv0vn+9/5=δ5n+1.
Then,f∗u0=22n+3/5δ, and f∗vn+9/5=19n+6/5δ.
In all cases,f∗v0 and f∗u0 are not congruent to f∗vi nor f∗uimod5n+1δ,i=1,2,3,⋯,n which completes the proof.Illustration 5. In Figure 10, we present PW6 with an edge 3− graceful labeling and PW8 with an edge 4− graceful labeling.Theorem 9.
For any positive integerδ, the prism of the wheel PWn is an edge δ− graceful graph, when n is odd.Proof.
Let the vertex and edge symbols be given as in Figure9. Define the labeling function f by
(27)fv0u0=δ,fviui=δn+ifori∈1,2,3,⋯,n,fv1vn=3nδ,fvivi+1=δ2n+ifori∈1,2,3,⋯,n−1,funu1=4nδ,fuiui+1=δ3n+ifori∈1,2,3,⋯,n−1,fv0v1=5nδ,fv0vi=δiifi=2,3,⋯,n+12,δ4n+i−1ifi=n+32,⋯,n,fu0un=5n+1δ,fu0ui=δn+12+iifi=1,2,3,⋯,n−12,δ7n+12+iifi=n+12,⋯,n−1.
In view of the above labeling pattern, we can check that(i)
fv0vi+fv0vn−i+2mod5n+1δ=0,i=2,3,⋯,n+1/2
(ii)
fu0ui+fu0un−imod5n+1δ=0,i=1,2,⋯,n−1/2
(iii)
fv0u0+fv0v1mod5n+1δ=0 then, the induced vertex labels are
(28)f∗v0=0,f∗u0=δ,f∗v1=nδ,f∗un=5n−2δ,f∗vn+1/2=2nδ,f∗vi=δ4i−2ifi=2,3,⋯,n+12,δ4i−n−4ifi=n+32,⋯,n,f∗ui=δ5n−32+4iifi=2,3,⋯,n−12,δn−52+4iifi=n+12,⋯,n−1.
Hence, the labels of the verticesv2,v3,⋯,vn+1/2 are 6δ,10δ,⋯,2nδ and the labels of the vertices vn+3/2,vn+5/2,⋯,vn are n+2δ,n+6δ,⋯,3n+4δ, respectively. Also, the labels of the vertices u2,u3,⋯,un−1/2 are 5n+13/2δ,5n+21/2δ,⋯,9n−7/2δ, and the labels of the vertices un+1/2,un+3/2,⋯,un−1 are 5n−1/2δ,5n+7/2δ,⋯,3n−13/2δ, respectively. There are no repeated vertex labels when n≡3mod8, i.e., n=8r+3.
Also in this labeling, there are two cases:Case 1.
Whenn≡1mod4, i.e., n=4r+1.
In this case, we havef∗u1 will equal to f∗ui when i=3n+5/4, so we change the labeling of two edges u0u1 and u0u2 as follows: fu0u1=n+5/2δ and fu0u2=n+3/2δ.
Then,f∗u1=7n+7/2δ, and f∗u2=5n+11/2δ.Case 2.
Whenn≡7mod8, i.e., n=8r+7.
In this case, we havef∗un+1/2 will equal to f∗vi when i=7n+7/8, so we change the labeling of two edges (u0un+1/2) and (u0un+3/2) as follows: fu0un+1/2=4n+2δ and fu0un+3/2=4n+1δ.
Then,f∗un+1/2=5n+1/2δ, and f∗un+3/2=5n+5/2δ.
Note thatPW3 does not follow this rule; however, it is an edge δ− graceful graph, as in Figure 11. In all cases, f∗v0 and f∗u0 are not congruent to f∗vi nor f∗uimod5n+1δ,i=1,2,3,⋯,n which completes the proof.Illustration 6. In Figure 12, we present PW7 with an edge 5− graceful labeling and PW9 with an edge 2− graceful labeling.Figure 9
The prism of the wheelPWn with ordinary labeling.Figure 10
PW6 with an edge 3− graceful labeling and PW8 with an edge 4− graceful labeling.Figure 11
An edgeδ− graceful labeling of the graph PW3.Figure 12
PW7 with an edge 5− graceful labeling and PW9 with an edge 2− graceful labeling.


## 7. Edgeδ− Graceful Labeling of the Gear Graph Gn

Theorem 10.
For any positive integerδ, the gear graph Gn is an edge δ− graceful graph.Proof.
The gear graphGn is the graph obtained from the wheel Wn by inserting a vertex between any two adjacent vertices in its cycle Cn; the gear graph Gn has p=2n+1 vertices and q=3n edges. Let the vertices of the wheel be v1,v2,⋯,vn, the hub vertex be v0, and the new vertices be u1,u2,⋯,un, so the edges will be v0vi,viui,uivi+1,i=1,2,⋯,n, see Figure 13.
We define the labeling functionf:EGn→δ,2δ,3δ,⋯,3nδ by
(29)fviui=δifori=1,2,⋯,n,fv0v1=δ3n−1,fv0vi=δn+2i−3,i=2,3,⋯,n,fu1v2=3nδ,fuivi+1=δ3n−2i,i=2,3,⋯,n.
So the induced vertex labels will be(30)f∗v1=0,f∗vi=δn+i−1mod3nδ,i=2,3,⋯,n,f∗un=nδ,f∗ui=δ3n−i,i=2,3,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn−1,vn are δn+1,δn+2,⋯,δ2n−2,δ2n−1, respectively, and the labels of the vertices u1,u2,⋯,un−2,un−1 are 3n−1δ,3n−2δ,⋯,δ2n+2,δ2n+1, respectively. Hence, there are no repeated vertex labels.
(31)f∗v0=∑i=1nfv0vimod3nδ=δn+δ+δn+3δ+δn+5δ+⋯+δn+2n−3δ+3δn−δmod3nδ=δnn−1+δ+3δ+5δ+⋯+2n−3δ+3δn−δmod3nδ=2n2δmod3nδ.Case 1.
Whenn≡1mod6 or n≡4mod6.
(i)
Ifn≡1mod6⇒n=6r+1⇒δq=3nδ=18rδ+3δ, then f∗v0=72r2δ+24rδ+2δmod18rδ+3δ≡12rδ+2δmod18rδ+3δ=2nδ
(ii)
Ifn≡4mod6, then f∗v0=2nδCase 2.
Whenn≡0mod6 or n≡3mod6.
(i)
Ifn≡0mod6⇒n=6r⇒δq=3nδ=18rδ, then f∗v0=72r2δmod18rδ≡0
(ii)
Ifn≡3mod6, then f∗v0=0
In this case, we havef∗v0 will equal to f∗v1, so we change the labeling of two edges v0v1 and unv1 as follows: fv0v1=3nδ and funv1=δ3n−1. Then, f∗v0=δ and f∗un=n−1δ.Case 3.
Whenn≡2mod6 or n≡5mod6.
(i)
Ifn≡2mod6⇒n=6r+2⇒δq=3nδ=18rδ+6δ, then f∗v0=72r2δ+48rδ+8δmod18rδ+6δ≡6rδ+2δmod18rδ+6δ=nδ
(ii)
Ifn≡5mod6, then f∗v0=nδ
In this case, we havef∗v0 will equal to f∗un, so we change the labeling of two edges v0v2 and vnun as follows: fv0v2=nδ and fvnun=δn+1. Then, f∗v0=δn−1, f∗un=n+1δ, f∗vn=2nδ, and f∗v2=nδ.
In all cases,f∗v0 is not congruent to f∗vi nor f∗uimod3nδ, i=1,2,3,⋯,n, and there are no repetition in the vertex labels which completes the proof.Illustration 7. In Figure 14, we present G10 with edge 7− graceful labeling, G9 with edge 4− graceful labeling, and G11 with edge 5− graceful labeling.Figure 13
The gear graphGn with ordinary labeling.Figure 14
The gear graphG10 with edge 7− graceful labeling, G9 with edge 4− graceful labeling, and G11 with edge 5− graceful labeling.


## 8. Edgeδ− Graceful Labeling of the Closed Helm CHn

The closed helmCHn is the graph obtained from a helm Hn by joining each pendent vertex to form a cycle; a closed helm has p=2n+1 vertices and q=4n edges.Theorem 11.
For any positive integerδ, the closed helm CHn is an edge δ− graceful graph.Proof.
In the closed helmCHn, we have two copies of the cycle Cn; let the vertices in the inside copy be v1,v2,⋯,vn and the vertices on the outside copy be u1,u2,⋯,un and a hub vertex v0; the edges will be v0vi,viui,vivi+1,uiui+1,i=1,2,⋯,n, see Figure 15.
We define the labeling functionf:ECHn→δ,2δ,3δ,⋯,4nδ by
(32)fv0vi=δifori∈1,2,3,⋯,n,fv1vn=3nδ,fvivi+1=δ2n+ifori∈1,2,3,⋯,n−1,fu1un=4nδ,fuiui+1=δ3n+ifori∈1,2,3,⋯,n−1,fv1u1=n+1δ,fuiui=δ2n−i+2fori∈2,3,⋯,n.
In view of the above labeling pattern, then the induced vertex labels are(33)f∗v1=δ2n+3,f∗vi=δ2n+2i+1mod4nδ,i=2,3,⋯,n,f∗u1=2δ,f∗ui=δi+1,i=2,3,⋯,n.
Hence, the labels of the verticesv2,v3,⋯,vn−1,vn will be δ2n+5,δ2n+7,⋯,δ4n−1,δ, respectively, and the labels of the vertices u2,u3,⋯,un−1,un will be 3δ,4δ,⋯,δn,δn+1, respectively.
(34)f∗v0=∑i=1nfv0vimod4nδ=∑i=1nδimod4nδ=δ2n2+nmod4nδ.Case 1.
Whenn≡2mod8 or n≡4mod8 or n≡3mod8 or n≡7mod8.
(i)
Ifn≡2mod8⇒n=8r+2⇒δq=4nδ=32rδ+8δ, then
(35)f∗v0=32r2δ+20rδ+3δmod32rδ+8δ≡12rδ+3δmod32rδ+8δ=3nδ2
(ii)
Ifn≡4mod8, then f∗v0=5nδ/2
(iii)
Ifn≡3mod8, then f∗v0=2nδ
(iv)
Ifn≡7mod8, then f∗v0=0Case 2.
Whenn≡0mod8. If n≡0mod8⇒n=8r⇒δq=4nδ=32rδ, then
(36)f∗v0=32r2δ+4rδmod32rδ≡4rδmod32rδ=nδ2.
In this case, we havef∗v0 will equal to f∗un−2/2, so we change the labeling of two edges (un−4/2un−2/2) and (unu1) as follows: fun−4/2un−2/2=4nδ and funu1=δ7n/2−2.
Then,f∗un−4/2−n+1δ, f∗un−2/2=n+2δ, f∗u1=7nδ/2, and f∗un=n/2−1δ.Case 3.
Whenn≡6mod8. If n≡6mod8⇒n=8r+6⇒δq=4nδ=32rδ+24δ, then
(37)f∗v0=32r2δ+52rδ+21δmod32rδ+24δ≡28rδ+21δmod32rδ+24δ=7nδ2.
In this case, we havef∗v0 will equal to f∗v3n−2/4, so we change the labeling of two edges v3n−2/4v3n+2/4 and v3n+2/4v3n+6/4 as follows: fv3n−2/4v3n+2/4=δ11n+2/4 and fv3n+2/4v3n+6/4=δ11n−2/4.
Then,f∗v3n−2/4=7n+2/2δ,f∗v3n+2/4=7n+4/2δ, and f∗v3n+6/4=7n+6/2δ.Case 4.
Whenn≡1mod8. If n≡1mod8⇒n=8r+1⇒δq=4nδ=32rδ+4δ, then f∗v0=32r2δ+12rδ+δmod32rδ+4δ≡8rδ+δmod32rδ+4δ=nδ.
In this case, we havef∗v0 will equal to f∗un−1, so we change the labeling of two edges (un−2un−1) and (unu1) as follows: fun−2un−1=4nδ and funu1=δ4n−2.
Then,f∗un−2=n+1δ, f∗un−1=n+2δ, f∗un=n−1δ, and f∗u1=0.Case 5.
Whenn≡5mod8. If n≡5mod8⇒n=8r+5⇒δq=4nδ=32rδ+20δ, then f∗v0=32r2δ+44rδ+15δmod32rδ+20δ≡24rδ+15δmod32rδ+20δ=3nδ.
In this case, we havef∗v0 will equal to f∗vn−1/2, so we change the labeling of two edges vn−5/2vn−3/2 and vn−3/2vn−1/2 as follows: fvn−5/2vn−3/2=δ/25n−3 and fvn−3/2vn−1/2=δ/25n−5.
Then,f∗vn−5/2=3n−3δ,f∗vn−3/2=3n−2δ and f∗vn−1/2=3n−1δ.
Clearly, in all cases,f∗v0 is not congruent to f∗vi nor f∗uimod4nδ, i=2,3,⋯,n, and all the labels of the vertices vi and ui are distinct and a multiplies of δ. Thus, the closed helm is an edge δ− graceful graph.Illustration 8. In Figure 16, we present CH11 with edge 7− graceful labeling, CH12 with edge 6− graceful labeling, CH8 with edge 5− graceful labeling, CH14 with edge 3− graceful labeling, CH9 with edge 5− graceful labeling, and CH13 with edge 5− graceful labeling, respectively.Figure 15
The closed helm CHn with ordinary labeling.Figure 16


## 9. Edgeδ− Graceful Labeling of the Friendship Frn

Theorem 12.
For any positive integerδ, the friendship graph Fn is an edge δ− graceful graph.Proof.
The friendship graphFn is a planar undirected graph constructed by joining n copies of cycle graph C3 with common vertex, so p=VFrn=2n+1 and q=EFrn=3n. Let the friendship graph Fn be given as in Figure 17 with central vertex v0, and the edges of Frn will be v0vi,v0ui,viui,i=1,2,⋯,n. There are two cases:Case 1.
n≡1mod3, or n≡2mod3.
We define the labeling functionf:EFrn→δ,2δ,⋯,3nδ as follows:
(38)fori=1,2,⋯,n,fviui=δi,fori=1,2,⋯,n,fv0vi=δn+2i−1,fori=1,2,⋯,n,fv0ui=δn+2i.
Then, the induced vertex labels are(39)f∗vi=fv0vi+fviuimod3nδ=δn+3i−1mod3nδ,i=1,2,⋯n,f∗ui=fv0ui+fviuimod3nδ=δn+3imod3nδ,i=1,2,⋯n.
Hence, the labels of the verticesv1,v2,v3,⋯,vn−1,vn are n+2δ, n+5δ, n+8δ,⋯,n−4δ, n−1δ, respectively, and the labels of the vertices u1,u2,u3,⋯,un−1,un will be n+3δ, n+6δ, n+9δ,⋯,n−3δ, nδ, respectively, which are all distinct numbers. Also,
(40)f∗v0=∑i=1nfv0vi+∑i=1nfv0uimod3nδ=δn+1+δn+2+δn+3+⋯+δn+2nmod3nδ=δ4n2+nmod3nδ.
(i)
Ifn≡1mod3⇒n=3r+1⇒qδ=3nδ=9rδ+3δ, then
(41)f∗v0=36r2δ+27rδ+5δmod9rδ+3δ≡6rδ+2δmod9rδ+3δ=2nδ
(ii)
Ifn≡2mod3, then f∗v0=0Case 2.
n≡0mod3. We define the labeling function f as follows:
(42)fori=1,2,⋯,n−1,fviui=δ2n+i+1,fvnun=δ,fori=1,2,⋯,n,fv0vi=δ2i,fori=1,2,⋯,n,fv0ui=δ2i+1.
In view of the above labeling pattern, then the induced vertex labels are(43)f∗vi=fv0vi+fviuimod3nδ=δ2n+3i+1mod3nδ,i=1,2,⋯,n,f∗ui=fv0ui+fviuimod3nδ=δ2n+3i+2mod3nδ,i=1,2,⋯,n.
Hence, the labels of the verticesv1,v2,v3,⋯,vn−1,vn are 2n+4δ, 2n+7δ, 2n+10δ,⋯,n−2δ,2n+1δ, respectively, and the labels of the vertices u1,u2,u3,⋯,un−1,un are 2n+5δ, 2n+8δ, 2n+11δ,⋯,2n−1δ, 2n+2δ, respectively, which are all distinct numbers.
(44)f∗v0=∑i=1nfv0vi+∑i=1nfv0uimod3nδ=2δ+3δ+4δ+⋯+δ1+2nmod3nδ=δ2n2+3nmod3nδ.
(i)
Ifn≡0mod3⇒n=3r⇒qδ=3nδ=9rδ, then f∗v0=18r2δ+9rδmod9rδ≡0
Overall, all the labels of the verticesvi and ui are all distinct, multiple of δ, and different from f∗v0 which completes the proof.Illustration 9. In Figure 18, we present the friendship graphs Fr9 with edge 5− graceful labeling and Fr10 with edge 6− graceful labeling.Figure 17
The friendship graph Frn with ordinary labeling.Figure 18
The friendship graphs Fr9 with edge 5− graceful labeling and Fr10 with edge 6− graceful labeling.


## 10. Edgeδ− Graceful Labeling of the Butterfly Graph Bn

Theorem 13.
For any positive integerδ, the butterfly graph Bn is an edge δ− graceful graph.Proof.
The butterfly graphBn is a planer graph constructed by joining 2n copies of cycle graph C3 with a common edge, a butterfly graph Bn has p=2n+2 vertices and q=4n+1 edges, let the common edge in all cycles be (v0u0) and the vertices of one copy be v1,v2,⋯,vn and the vertices of the other copy be u1,u2,⋯,un; the edges will be {v0vi,u0vi,u0ui,v0ui,v0u0, i=1,2,⋯,n}, see Figure 19. There are two cases:Case 1.
Whenn is even. Define the labeling function f:EBn→δ,2δ,3δ,⋯,4n+1δ as follows:
(45)fu0vi=δi,fori=1,2,⋯,n,fv0vi=δ2n+i,fori=1,2,⋯,n,fu0ui=δ3n+i,fori=1,2,⋯,n,fv0u0=2nδ,fv0u1=4n+1δ,‘fv0ui=δn+i−1,ifi=2,3,⋯,n.
In view of the above labeling pattern, then the induced vertex labels are(46)f∗vi=fv0vi+fu0vimod4n+1δ=2δn+i,i=1,2,⋯n,f∗u1=δ3n+1,‘f∗ui=2δi−1,i=2,3,⋯n,
In this labeling, we can check that(47)fv0vi+fv0un+2−1mod4n+1δ≡0mod4n+1δ,i=2,3,⋯,n,fu0ui+fu0un+1−imod4n+1δ≡0mod4n+1δ,i=1,2,⋯,n.
Then(48)f∗v0=∑i=1nfv0vi+∑i=1nfv0ui+fv0u0mod4n+1δ=0,f∗u0=∑i=1nfu0vi+∑i=1nfu0ui+fv0u0mod4n+1δ=2nδ.Case 2.
Whenn is odd. By using the same labeling as in the first case, in this case, we have f∗u0 will equal to f∗vn+1/2, so we change the labeling of two edges (v0u0) and (v0u1) as follows: fv0u0=δn+1 and fv0u1=δ4n+1, then f∗u1=δ, and f∗u2=3n+2δ.
We can see that the labels of the verticesvi, and ui, i=1,2,⋯,n are all a multiple of δ and distinct numbers and different from the labels of the vertices v0 and u0. Hence, the butterfly graph Bn is an edge δ− graceful graph, for any positive integer δ.Illustration 10. In Figure 20, we present B10 with edge 5− graceful labeling and B9 with edge 4− graceful labeling.Figure 19
The butterfly graphBn with ordinary labeling.Figure 20
B10 with edge 5− graceful labeling and B9 with edge 4− graceful labeling.


## 11. Conclusion

In the past few years, edge graceful labeling of graphs has been studied heavily and these topics continue to be attractive in the field of graph theory and discrete mathematics. A great number of published papers and results exist. So far, many graphs are unknown if it is edge graceful or not.In this work, a new type of labeling called edgeδ− graceful labeling is defined; the graph which satisfies the edge δ− graceful labeling is called an edge δ− graceful graph. Edge δ− graceful labeling of some special classes of graphs like wheel graph, double wheel, prism graph, gear graph, closed helm, friendship graph, and butterfly graph is investigated. In future work, we will study the necessary and sufficient conditions for some path-related graph to be an edge δ− graceful graph.



---

*Source: 6273245-2020-01-20.xml*