Edge-Graceful Labelings of Connected Graphs

Edge-Graceful Labelings of Connected Graphs

Available online at www.sciencedirect.com Electronic Notes in Discrete Mathematics 53 (2016) 287–296 www.elsevier.com/locate/endm Edge-Graceful Labe...

208KB Sizes 1 Downloads 31 Views

Available online at www.sciencedirect.com

Electronic Notes in Discrete Mathematics 53 (2016) 287–296 www.elsevier.com/locate/endm

Edge-Graceful Labelings of Connected Graphs K.Kayathri 1 PG & Research Department of Mathematics Thiagarajar College, Madurai Tamil Nadu, India

R. Amutha 2,3 Department of Mathematics N.M.S.S.Vellaichamy Nadar College Madurai, Tamil Nadu, India

Abstract Let G be a connected edge-graceful (p, q)-graph with q = kp + r, where k is an integer and 0 ≤ r < p. In this paper, we prove that every edge-graceful labeling f of G induces [(k + 1)!]r [k!]p−r number of edge-graceful labelings of G. Keywords: edge-graceful labeling, edge label, vertex label

1

Introduction

Rosa[2] introduced the concept of graceful labeling as a means of attacking the problem of cyclically decomposing the complete graph into other graphs. 1 2 3

Email: [email protected] Research supported by UGC-SERO under FDP of XII plan Email: [email protected]

http://dx.doi.org/10.1016/j.endm.2016.05.024 1571-0653/© 2016 Elsevier B.V. All rights reserved.

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

288

In 1985, Sheng-Ping Lo[3] introduced a similar concept called edge-graceful labeling. A (p, q)-graph G is said to be edge-graceful if there exists a bijection f : E → {1, 2, ..., q} such that the induced mapping f  : V → {0, 1, 2, ..., p − 1}  defined by f  (v) = f (e) (mod p) is also a bijection. e=(v,u)∈E

A necessary condition for edge-gracefulness of a (p, q)-graph G is q(q +1) ≡ p(p − 1)/2 (mod p)[3]. A detailed list of edge-graceful graphs is given in Gallian Survey of Graph Labelings[1]. In this paper, we derive new edge-graceful labelings from a known edgegraceful labeling. We first start with edge-graceful trees and unicyclic graphs and then extend for all edge-graceful connected graphs. We also enumerate the induced edge-graceful labelings of connected graphs. For notational convenience, we denote the set of all edges incident with v  as N (v), for every v ∈ V .

2

Edge-Graceful Labelings of Trees and Unicyclic Graphs

Theorem 2.1 Let f be an edge-graceful labeling of a tree G with p vertices.Then the labeling F defined by F (e) = p − f (e) is also an edge-graceful labeling.    Proof. For the induced map F , F  (v) ≡ F (e) ≡ (p−f (e)) (mod p) 

e∈N  (v)

e∈N  (v)

= p − f  (v). As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so  also F . Hence F is also an edge-graceful labeling of G. 2 Theorem 2.2 Let f be an edge-graceful labeling⎧of an unicyclic graph with p ⎨ p − f (e) if f (e) < p vertices. Then the labeling F defined by F (e) = ⎩ f (e) if f (e) = p is also an edge-graceful labeling. Proof. Suppose that the edge (w1 , w2 ) has the label p, where w1 , w2 ∈ V. Case (i) v ∈ / {w1 , w2 } .    F (e) ≡ (p − f (e)) (mod p) For the induced map F , F  (v) ≡ 

= p − f (v). Case (ii) v ∈ {w1 , w2 } .

e∈N  (v)

e∈N  (v)

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

289



For the induced map F ,  F  (v) ≡ F (e) ≡ p+ (p − f (e)) (mod p)   e∈N (v) e∈N (v)−{(w1 ,w2 )}   ≡ − f (e) ≡ p − f (e) (mod p) = p − f  (v). 

e∈N (v)−{(w1 ,w2 )}





e∈N (v)



As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also F . Hence F is also an edge-graceful labeling of G. 2

3

Edge-Graceful Labelings of Connected Graphs

In this section, we prove that every edge-graceful labeling induces new edgegraceful labelings, in which only the edge labels vary, but the vertex labels remain the same. Theorem 3.1 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp + r, where k and r are integers with k > 1, 0 ≤ r < p.⎧F or 0 ≤ l < m ≤ k − 1, define a labeling Fl,m such that ⎪ ⎪ f (e) + (m − l)p if f (e) = lp + i ⎪ ⎨ Fl,m (e) = f (e) + (l − m)p if f (e) = mp + i ⎪ ⎪ ⎪ ⎩ f (e) otherwise where 1 ≤ i ≤ p. Then Fl,m is also an edge-graceful labeling of G. Proof. For 0 ≤ l ≤ k − 1, let El = {e ∈ E | f (e) = lp + i, 1 ≤ i ≤ p}; and k−1  let Ek = {e ∈ E | f (e) = kp + i, 1 ≤ i ≤ r}, so that E = ( El ) ∪ Ek . 

l=0

For the induced  map Fl,m ,  Fl,m (v) ≡ Fl,m (e) (mod p) e∈N  (v)    ≡ Fl,m (e) + Fl,m (e) + Fl,m (e) (mod p)    e∈N (v)∩El e∈N (v)∩Em e∈N (v)−(El ∪Em )   (f (e) + (m − l)p) + (f (e) + (l − m)p) ≡ e∈N  (v)∩El e∈N  (v)∩Em  + f (e) (mod p)  e∈N (v)−(El ∪Em )    f (e) + f (e) + f (e) (mod p) ≡ e∈N  (v)∩El e∈N  (v)∩Em e∈N  (v)−(El ∪Em )  f (e) (mod p) = f  (v). ≡ 

e∈N (v) 

 . Hence As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also Fl,m Fl,m is also an edge-graceful labeling of G. 2

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

290

Theorem 3.2 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp + r, where k and r are integers with k ≥ 1, 1 ≤ r < p. For 0 ≤ ⎧ l ≤ k − 1, define a labeling Fl such that ⎪ ⎪ f (e) + (k − l)p if f (e) = lp + i ⎪ ⎨ Fl (e) = f (e) + (l − k)p if f (e) = kp + i ⎪ ⎪ ⎪ ⎩ f (e) otherwise where 1 ≤ i ≤ r. Then Fl is also an edge-graceful labeling of G. Proof. For 0 ≤ l ≤ k − 1, let El = {e ∈ E | f (e) = lp + i, 1 ≤ i ≤ p}; and k−1  let Ek = {e ∈ E | f (e) = kp + i, 1 ≤ i ≤ r}, so that E = ( El ) ∪ Ek . Note l=0

that, under Fl , the edge labels lp + (r + 1), lp + (r + 2), ..., (l + 1)p of edges in El remain the same.  For the induced map Fl ,  Fl (v) ≡ Fl (e) (mod p)  e∈N (v)    Fl (e) + Fl (e) + Fl (e) (mod p) ≡    e∈N (v)∩El e∈N (v)∩Ek e∈N (v)−(El ∪Ek )   ≡ (f (e) + (k − l)p) + f (e)   e∈N (v)∩El ,1≤i≤r e∈N (v)∩El ,r+1≤i≤p   (f (e) + (l − k)p) + f (e) (mod p) +   e∈N (v)∩Ek e∈N (v)−(El ∪Ek )    ≡ f (e) + f (e) + f (e) (mod p)    e∈N (v)∩El e∈N (v)∩Ek e∈N (v)−(El ∪Ek )  f (e) (mod p) = f  (v). ≡ e∈N  (v) 

As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also Fl . Hence Fl is also an edge-graceful labeling of G. 2 Theorem 3.3 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp, where k > 1 is an integer. Let S denote the set of all permutations defined on {0, 1, 2, ..., k − 1}. For every π ∈ S, define a labeling Fπ such that Fπ (e) = f (e) + (π(l) − l)p if f (e) = lp + i, where 1 ≤ i ≤ p and 0 ≤ l ≤ k − 1. Then Fπ is also an edge-graceful labeling of G. Proof. For 0 ≤ l ≤ k −1, let El = {e ∈ E | f (e) = lp + i, 1 ≤ i ≤ p}, so that k−1  E = ( El ) ∪ Ek . l=0



For the induced map Fπ ,

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296



Fπ (v) ≡ ≡



Fπ (e) ≡

e∈N (v)

k−1 



l=0 e∈N  (v)∩El 

k−1 



l=0 e∈N  (v)∩El

(f (e)+(π(l)−l)p) ≡

291

Fπ (e) (mod p) k−1 



l=0 e∈N  (v)∩El

f (e) ≡

 

f (e) (mod p)

e∈N (v)

= f (v).  As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also Fπ . Hence Fπ is also an edge-graceful labeling of G. 2 Theorem 3.4 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp + r, where k and r are integers with k > 1 and 1 ≤ r < p.   Let S denote the set of all permutations defined on {0, 1, 2, ..., k}. Let π ∈ S and m and n be integers such that π(n) = k and π(k) = m. Then a labeling Fπ defined ⎧ by ⎪ ⎪ f (e) + (π(l) − l)p if f (e) = lp + i, 1 ≤ i ≤ p, l = n, 0 ≤ l ≤ k − 1 ⎪ ⎪ ⎪ ⎪ ⎨ f (e) + (k − n)p if f (e) = np + i, 1 ≤ i ≤ r Fπ (e) = ⎪ ⎪ f (e) + (m − n)p if f (e) = np + i, r + 1 ≤ i ≤ p ⎪ ⎪ ⎪ ⎪ ⎩ f (e) + (m − k)p if f (e) = kp + i, 1 ≤ i ≤ r is also an edge-graceful labeling of G. Proof. For 0 ≤ l ≤ k − 1, let El = {e ∈ E | f (e) = lp + i, 1 ≤ i ≤ p}; and k−1  let Ek = {e ∈ E | f (e) = kp + i, 1 ≤ i ≤ r}, so that E = ( El ) ∪ Ek . l=0



For the induced mapFπ ,   Fπ (v) ≡ Fπ (e) (mod p) e∈N  (v)    ≡ Fπ (e) + Fπ (e) + Fπ (e) (mod p)    e∈N (v)∩En e∈N (v)∩Ek e∈N (v)−(En ∪Ek )   (f (e) + (k − n)p) + (f (e) + (m − n)p) ≡ 



e∈N (v)∩En ,1≤i≤r



+



(f (e) + (m − k)p) +

e∈N (v)∩Ek



≡ ≡



e∈N (v)∩En

 

e∈N (v) 



f (e) +



e∈N (v)∩Ek

f (e) (modp)

e∈N (v)∩En ,r+1≤i≤p k−1   l=0,l=n e∈N  (v)∩El

f (e) +

= f  (v).

k−1 

(f (e) + (π(l) − l)p) (mod p)



l=0,l=n e∈N  (v)∩El

f (e) (mod p)

As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also Fπ . Hence Fπ is also an edge-graceful labeling of G. 2

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

292

Theorem 3.5 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp + r, where k and r are integers with 0 ≤ r < p. Let 1 ≤ i ≤ p. (i) Define a labeling Fl,m such that ⎧ ⎪ f (e) + (m − l)p if f (e) = lp + i ⎪ ⎪ ⎨ (i) Fl,m (e) = f (e) + (l − m)p if f (e) = mp + i ⎪ ⎪ ⎪ ⎩ f (e) otherwise where l and m are integers satisfying 0 ≤ l < m ≤ k if i ≤ r; and (i) 0 ≤ l < m ≤ k − 1 if i > r. Then Fl,m is also an edge-graceful labeling of G. Proof. Let e1 , e2 be the edges with f (e1 ) = lp + i and f (e2 ) = mp + i. For every v ∈ V , we have one of the following four cases:     (i) e1 ∈ N (v), e2 ∈ / N (v), (ii) e1 ∈ / N (v), e2 ∈ N (v),   (iii) e1 , e2 ∈ N (v), (iv) e1 , e2 ∈ / N (v).   Case (i) e1 ∈ N (v), e2 ∈ / N (v)  (i) For the induced map Fl,m ,   (i) (i) Fl,m (v) ≡ Fl,m (e) (mod p) 



e∈N (v) (i) Fl,m (e1 )



(i)

Fl,m (e)(mod p)  e∈N (v)−{e1 }  f (e)(mod p) ≡ f (e1 ) + (m − l)p + e∈N  (v)−{e1 }  ≡ f (e1 ) + f (e)(mod p)  e∈N (v)−{e1 }  f (e) (mod p) = f  (v). ≡ +

e∈N  (v)

Proof is similar in all the other cases.  (i)  As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also Fl,m . Hence (i)

Fl,m is also an edge-graceful labeling of G.

2

Theorem 3.6 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp, where k is an integer with k > 1. Let S denote the set of all permutations defined on {0, 1, 2, ..., k − 1}. Let 1 ≤ i ≤ p. For any π ∈ S, (i) define a labeling Fπ such that ⎧ ⎨ f (e) + (π(l) − l)p if f (e) = lp + i (i) Fπ (e) = ⎩ f (e) otherwise (i)

where 0 ≤ l ≤ k − 1. Then Fπ is also an edge-graceful labeling of G.   Proof. Let Ei | 1 ≤ i ≤ p be a partition of E, where

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

293



Ei = {e ∈ E| f (e) = lp + i, 0 ≤ l ≤ k − 1} , 1 ≤ i ≤ p.  (i) For the induced map Fπ ,   (i) (i) Fπ (v) ≡ F(π) (e) (mod p) 

e∈N (v)





(i)



(i)

Fπ (e)(mod p) e∈N e∈N   ≡ (f (e) + (π(l) − l)p) + f (e)(mod p)     e∈N (v)∩Ei e∈N (v)−Ei   ≡ f (e) + f (e)(mod p)     e∈N (v)∩Ei e∈N (v)−Ei  ≡ f (e) (mod p) = f  (v). 

 (v)∩Ei

F(π) (e)+



 (v)−Ei



e∈N (v)

 (i)



As f is a bijection map with the range {0, 1, 2, ..., p − 1} , so also Fπ . Hence (i) Fπ is also an edge-graceful labeling of G. 2 Theorem 3.7 Let f be an edge-graceful labeling of a connected (p, q)-graph G  with q = kp + r, where 1 ≤ r < p, k is an integer with k ≥ 1. Let S, S be the set of all permutations defined on the sets {0, 1, 2, ..., k − 1} and {0, 1, 2, ..., k}  respectively. For 1 ≤ i ≤ p, choose π ∈ S or S in accordance with 1 ≤ i ≤ r (i) or r + 1 ≤⎧i ≤ p. Define a labeling Fπ such that ⎨ f (e) + (π(l) − l)p if f (e) = lp + i (i) Fπ (e) = ⎩ f (e) otherwise where 0 ≤ l ≤ k if 1 ≤ i ≤ r; and 0 ≤ l ≤ k − 1 if r + 1 ≤ i ≤ p. (i) Then Fπ is also an edge-graceful labeling of G.   | 1 ≤ i ≤ p be a partition of E, where Proof. Let E i ⎧ ⎨ {e ∈ E | f (e) = lp + i, 0 ≤ l ≤ k} , for 1 ≤ i ≤ r  Ei = ⎩ {e ∈ E | f (e) = lp + i, 0 ≤ l ≤ k − 1} , for r + 1 ≤ i ≤ p 

Note that, when 1 ≤ i ≤ r, then π ∈ S and the edge labels i, p + i, 2p + i, ..., kp + i are changed as π(0)p + i, π(1)p + i, π(2)p + i, ..., π(k)p + i respectively. Similarly, when r + 1 ≤ i ≤ p, then π ∈ S and the edge labels i, p + i, 2p + i, ..., (k − 1)p + i are changed as π(0)p + i, π(1)p + i, π(2)p + i, ..., π(k − 1)p + i respectively. (i) For the induced map Fπ ,   (i) (i) Fπ (v) ≡ F(π) (e) (mod p) 

e∈N (v)





(i)



e∈N  (v)∩Ei

F(π) (e) +



(i)



e∈N  (v)−Ei

Fπ (e) (mod p)

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

294



 (f (e) + (π(l) − l)p) + f (e)(mod p)     e∈N (v)∩Ei e∈N (v)−Ei   ≡ f (e) + f (e)(mod p)     e∈N (v)∩Ei e∈N (v)−Ei  ≡ f (e) (mod p) = f  (v). ≡



e∈N (v)

 (i)



As f is a bijection map with the range {0, 1, 2, ..., p − 1} , so also Fπ . Hence (i) Fπ is also an edge-graceful labeling of G. 2 Theorem 3.8 Let f be an edge-graceful labeling of a connected (p, q)-graph G with q = kp + r, where 0 ≤ r ≤ p and k is an integer with k ≥ 1. Let  S, S be the set of all permutations defined on the sets {0, 1, 2, ..., k − 1} and {0, 1, 2, ..., k} respectively. For any p-tuple (π1 , π2 , ..., πp ), where π1 , π2 , ..., πr ∈  S and πr+1 , πr+2 , ..., πp ∈ S, define a labeling F(π1 ,π2 ,...,πp ) such that F(π1 , π2 , ... , πp ) (e) = f (e) + (πi (l) − l)p if f (e) = lp + i, where 0 ≤ l ≤ k if 1 ≤ i ≤ r; and 0 ≤ l ≤ k − 1 if r + 1 ≤ i ≤ p. Then F(π1 , π2 , ... , πp ) is also an edge graceful labeling of G.   Proof. Let E | 1 ≤ i ≤ p be a partition of E, where i ⎧ ⎨ {e ∈ E | f (e) = lp + i, 0 ≤ l ≤ k} , for 1 ≤ i ≤ r and  Ei = ⎩ {e ∈ E | f (e) = lp + i, 0 ≤ l ≤ k − 1} , for r + 1 ≤ i ≤ p 

For the induced map F(π1 , π2 , ... , πp ) ,   F(π1 , π2 , ... , πp ) (v) ≡ F(π1 , π2 , ... , 

≡ ≡ ≡ ≡ 

e∈N (v)

p 



i=1 e∈N  (v)∩E  p 

 



e∈N (v)

(mod p)

(f (e) + (πi (l) − l)p) (mod p)

i

i=1 e∈N  (v)∩E 



π2 , ... , πp ) (e)

(mod p)

i

i=1 e∈N  (v)∩E  p 

F(π1 ,

πp ) (e)

f (e)(mod p)

i

f (e) (modp)

= f  (v). 

As f is a bijection map with the range {0, 1, 2, ..., p − 1}, so also F(π1 , Hence F(π1 , π2 , ... , πp ) is also an edge-graceful labeling of G.

π2 , ... , πp ) .

2

Note 1 All edge-graceful labelings defined in Theorems 3.1 to 3.7, are derivable from the edge-graceful labeling F(π1 , π2 , ... , πp ) defined in Theorem 3.8. For the labeling Fl,m in Theorem 3.1, we have Fl,m = F(π1 , π2 , ... , πp ) , where

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

πi =

⎧ ⎨π

295

if 1 ≤ i ≤ r

⎩ π|S if r + 1 ≤ i ≤ p 

and π ∈ S is the permutation with π(l) = m, π(m) = l and π(j) = j otherwise. For ⎧ the labeling Fl in Theorem 3.2, we have Fl = F(π1 , π2 , ... , πp ) , where ⎨ π if 1 ≤ i ≤ r πi = ⎩ the identity permutation on S if r + 1 ≤ i ≤ p 

and π ∈ S is the permutation with π(l) = k, π(k) = l and π(j) = j otherwise. For the labeling Fπ in Theorem 3.3, we have Fπ = F(π1 , π2 , ... , πp ) , where πi = π f or 1 ≤ i ≤ p. For ⎧ the labeling Fπ in Theorem 3.4, we have Fπ = F(π1 , π2 , ... , πp ) , where ⎪ ⎪ π(l) if 1 ≤ i ≤ r ⎪ ⎨ πi (l) = π(l) if r + 1 ≤ i ≤ p, l = n, ⎪ ⎪ ⎪ ⎩ π(π(l)) if r + 1 ≤ i ≤ p, l = n. (i)

(i)

For the labeling Fl,m in Theorem 3.5, we have Fl,m = F(π1 , ⎧ ⎨ identity permutation if j = i πj = ⎩π if j = i

π2 , ... , πp ) ,

where



and π ∈ S is the permutation with π(l) = m, π(m) = l and π(j) = j otherwise. (i) (i) For the labeling Fπ in Theorems 3.6 and 3.7, we have Fπ = F(π1 , π2 , ... , πp ) , ⎧ ⎨ identity permutation if j = i where πj = ⎩π if j = i.

4

Enumeration of induced edge-graceful labelings

Theorem 4.1 Let G be a edge-graceful connected (p, q)-graph with q = kp+r, where 0 < r ≤ p, k ≥ 1, k and r are integers. Then every edge-graceful labeling of G induces [(k + 1)!]r [k!]p−r distinct edge-graceful labelings for G. Proof. By Theorem 3.8, for each p-tuple (π1 , π2 , ... , πp ), where π1 , π2 , ... ,  πr ∈ S and πr+1 , πr+2 , ... , πp ∈ S, there is an edge-graceful labeling  F(π1 , π2 , ... , πp ) . As S has k + 1 elements and S has k elements, the num ber of permutations defined on S is (k + 1)! and on S is k!. Hence the number of possible p-tuples is [(k + 1)!]r [k!]p−r . Hence it is enough to show that the

296

K. Kayathri, R. Amutha / Electronic Notes in Discrete Mathematics 53 (2016) 287–296

labelings are distinct. Consider two distinct p-tuples (π1 , π2 , ... , πp ) and     (π1 , π2 , ..., πp ). Then πn = πn for some n, 1 ≤ n ≤ p. Therefore there exists  m such that πn (m) = πn (m) where m is an integer satisfying 0 ≤ m ≤ k if n ≤ r, 0 ≤ m ≤ k − 1 if r + 1 ≤ n ≤ p. Choose e ∈ E such that f (e) = mp + n. Now F(π1 , π2 , ... , πp ) (e) = f (e) + (πn (m) − m)p and F(π , π , ... , πp ) (e) = f (e) + 

1



2

(πn (m) − m)p. As πn (m) = πn (m), F(π1 , π2 , ... , πp ) (e) = F(π , π , ... , πp ) (e). 1 2 Therefore F(π1 ,π2 ,...,πp ) = F(π , π , ... , πp ) . Hence the number of edge graceful 1 2 2 labelings induced by f is [(k + 1)!]r [k!]p−r .

References [1] J.A.Gallian, A Dynamic Survey of Graph labelings, The Electronic journal of Combinatorics, 17 (2014) #D56. [2] A. Rosa, On certain valuations of the vertices of a graph,Theory of Graphs (International Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod, Paris, (1967). [3] Sheng-Ping Lo, On edge-graceful Numerantium, 50 (1985).

labelings

of

Graphs,

Congressus