Edge-Odd Gracefulness of Middle Graphs and Total Graphs of Paths and Cycles

Edge-Odd Gracefulness of Middle Graphs and Total Graphs of Paths and Cycles

S.Padmapriya , Dr.B.Sooryanarayana ,

Assistant Professor, Professor and Head,

Department of Mathematics, Department of Mathematical and Sir M Visvesvaraya Institute Computational Studies,

of Technology, Dr.Ambedkar Institute Of Technology,

Bangalore, India Bangalore, India

Abstract

Graph theory is rapidly moving into the mainstream of mathematics mainly because of its applications in diverse fields which include biochemistry (genomics), electrical engineering (communication network and coding theory), computer science (algorithms and computations) and operations research (scheduling). The recent applications of graph theory are DNA sequencing (SNP assembly problem), computer network (worm propagation) and assignment of frequencies in GSM mobile networks [6]. For a simple, finite, undirected and connected graph G(V,E), an Edge Odd Graceful labeling (EOGL) is an injective function f: E(G) {1,3,5,,2q1} such that the induced function f + : V(G) {0,1,2,…2k-1} defined by f +(x) = xy E(G) f(xy) (mod 2k) is injective where k=max{p,q}. A graph which admits an Edge Odd Graceful labeling is called an Edge Odd Graceful Graph (EOGG) [2]. In this paper, the Edge Odd Gracefulness of Middle Graphs and Total graphs of Paths and Cycles are obtained.

Keywords: Graceful graph, Edge odd graceful labelling, Edge odd graceful graph, Middle graph, Total graph.

AMS Classification Number: 05C78

1. Introduction

   In Graph theory, labelled graphs are the most useful mathematical models in addressing and identification system on a communication network to a larger network obtained by introducing new user terminals and new communication links between the new terminals of the original network. Also labelled graphs serve as useful models for coding theory, X-Ray, radars, astronomy, circuit design, crystallography, network addressing, database management, secret sharing schemes, etc.,[7]. A.Solairaju and K.Chitra [2] introduced and obtained edge-odd graceful labelling of some graphs related to paths. The results on edge-odd graceful labelling are given in Gallian survey [5].

   All the graphs considered in this paper are simple, undirected, finite and connected. The terms not defined here may be found in [4].

   Definition 1.1: Graceful Graph: [1][5]

   A (p,q) connected graph G is said to be a graceful graph if there exists an injective function f from the vertex set of G to the set {0, 1, 2, , q} such that when each edge uv is assigned the label |f(u)- f(v) and the resulting edge labels are distinct.

   Definition 1.2. Edge odd graceful graph: [2][3]

   A (p,q) connected graph G is said to be an edge-odd graceful graph if there exists an injective function f : E(G) {1,3,5,…,2q-1} such that the

   induced function f + : V(G) {0,1,2,3,…2k-1}, defined by f +(x) xy E(G) f(xy) (mod 2k) where

   k = max{p,q} is also injective.

   Definition 1.3. Middle graph: [9]

   Let G be a graph with vertex set V(G) and edge set E(G). The middle graph of G, denoted by M(G) is defined as follows. The vertex set of M(G) is V(G) U E(G). Two vertices x, y in the vertex set of M(G) are adjacent in M(G) in case one of the following holds: (i) x, y are in E(G) and x ,y are adjacent in G. (ii) x is in V(G), y is in E(G) and x, y are incident in G.

   Definition 1.4. Total Graph: [9]

   Let G be a graph with vertex set V (G) and edge set E(G). The total graph of G, denoted by T(G) is defined as follows. The vertex set of T(G) is V(G) U E(G). Two vertices x, y in the vertex set of T(G) are adjacent in T(G) in case one of the following holds:

   (i) x ,y are in V(G) and x is adjacent to y in G. (ii) x, y are in E(G) and x, y are adjacent in G. (iii) x is in V(G), y is in E(G) and x, y are incident in G.

2. Results on Middle Graphs of Paths and Cycles:

   Theorem 2.1.The Middle Graph of path Pn for n = 3, 4, 5, 6, 7, 8 and n 2 (mod 4) is edge odd graceful.

   Proof: From the diagram, the middle graph of the path

   P3 is EOG.

   Under (mod 10)

   Figure 1. Middle graph of P3

   The total number of edges in M(Pn) is (3n 4).

   For n >3 and n 2 (mod 4), define a function f : E(M(Pn)): {1,3,…,6n-9} such that the edges are labeled as

   f (viui) (6i-5) mod (6n-8) for 1 i n-1, f (uivi+1) (6i-1) mod (6n-8) for 1 i n-2, f (un-1vn) (6n-9) mod (6n-8) and

   f (uiui+1) (6i-3) mod (6n-8) for 1 i n-2.

   Define f + : V(M(Pn)) {0,1,2,3,…6n-9} such that the vertices are labeled as

   f +(v1) = 1, f +(vn) (6n-9) mod (6n-8), f +(vi) 6i mod (6n-8) for 2 i n-1,

   f +(ui) (24i-18) mod (6n-8) for 2 i n-2, f +(u1) = 9 and f+(un-1) (6n-19) for n 4

   Hence the induced map f + provides the distinct labels for vertices. Also edge labels are distinct.

   Thus M(Pn) for n = 3,4,5,6,7,8 and n 2 (mod 4) is Edge Odd Graceful.

   Theorem2.2.For all n 3, the middle graph of cycle Cn for odd n is Edge Odd Graceful.

   Proof: From the diagram, the middle graph of C3 is EOG.

   Under (mod 18)

   Figure 2. Middle graph of C3

   The Total number of edges in M(Cn) = 3n.

   For all odd n > 3, define a function

   f : E(M(Cn)): {1,3,…,6n-1} such that the edges are labeled as

   f (unv1) =1,

   f (uivi+1) (6i+1) mod 6n for 1i (n-1),

   f (vi ui) (6i-3) mod 6n for 1i n,

   f (uiui+1) (6i+5) mod 6n for 1i (n-1) and

   f (unu1)=5.

   Define f + : V(M(Cn)) {0,1,2,3,…6n-1} such that the vertices are labeled as

   f +(vi) (12i-8) mod 6n for 1i n, f +(ui) (24i+2) mod 6n for 1in .

   Hence the induced map f + provides the distinct labels for vertices. Also edge labels are distinct.

   Thus for all odd n, M(Cn) is Edge Odd graceful.

3. Results on Total graphs of Paths and Cycles:

Theorem 3.1.For all n 3, the total graph of a path Pn is Edge Odd Graceful.

Proof:

The Total number of edges in T (Pn) = 4n-5.

For n 3, define a function

f : E(T(Pn)): {1,3,…,8n-11} such that the edges are labeled as

f (vi ui ) (8i-7) mod (8n-10) for 1i (n-1),

f (uivi+1) (8i-3) mod (8n-10) for 1i (n-1),

f (vivi+1) (8i-5) mod (8n-10) for 1i (n-1) and

f (uiui+1) (8i-1) mod (8n-10) for 1i (n-2)

Define f + : V(T(Pn)) {0,1,2,3,…8n-11} such that the vertices are labeled as

f +(v1)=4, f +(vn)(8n-14) mod (8n-10) ,

f +(vi) (32i-36) mod (8n-10) for 2i (n-1),

f +(ui) (32i-20) mod (8n-10) for 2i (n-2), f +(un-1) (8n-23) mod (8n-10) for n 3 and f +(u1)=13.

Hence the induced map f + provides the distinct labels for vertices. Also edge labels are distinct.

Thus for all n 3, the total graph of Pn , T(Pn) is Edge Odd Graceful.

Example 3.2.

The total graph of a path P4 is EOG.

Under (mod 22)

Figure 3. Total graph of P4

Theorem 3.3.For a given odd integer n3, the total graph of cycle Cn is Edge Odd Graceful.

Proof:

The Total number of edges in T(Cn) is 4n.

For n 3, define a function f : E(T(Cn)):{1,3,…,8n-1} such that the edges are labeled as

f (unv1) =1, f(vnv1) 8n-1, f(unu1) =5 ,

f (vi vi+1 ) (8i-1) mod 8n for 1 i (n-1), f (uivi+1) (8i+1) mod 8n for 1 i (n-1), f (vi ui) (8i-5) mod 8n for 1 i n and

f (uiui+1) (8i+5) mod 8n for 1 i (n-1)

Define f + : V(T(Cn)) {0,1,2,3,…8n-1} such that the vertices are labeled as

f +(vi)(32i-22) mod 8n for 1i n,

f +(ui)(32i-2) mod 8n fo 2i (n-1) and

f +(un) (8n-2) mod 8n.

Hence the induced map f + provides the distinct labels for vertices. Also edge labels are distinct.

Thus for all odd n, the total graph of Cn, T(Cn) is Edge Odd Graceful.

Example 3.4.

The total graph of a cycle C7 is EOG.

Under (mod 56)

Figure 4. Total graph of C7

Acknowledgement

The authors are thankful to the anonymous referee for valuable comments and kind suggestions.

References

1. A.Solairaju and A.Sathik Batcha, Edge odd gracefulness of Halin Graphs of types H (4,n) and H(5, n) by International Journal of open problems in Mathematics andApplications,Vol.1,No.1,March 2011.

2. A.Solairaju and K.Chitra Edge-odd graceful labeling of some graphs Electronics Notes in Discrete Mathematics,Volume 33,April 2009, Pages 15 20.

3. A.Solairaju, A.Sasikala, C.Vimala Edge-odd Gracefulness of a spanning tree of Cartesian product of P2 and Cn, Pacific-Asian journal of Mathmatics, Vol .3, No. 1-2, (Jan-Dec. 2009) ,Pages:39 42.

4. Frank Harary, Graph Theory, Narosa Publishing House, Tenth Reprint, 2000.

5. Joseph A. Gallian, A Dynamic Survey of Graph Labeling, the electronic journal of combinatorics 17 (2010), #DS6, Thirteenth edition, November 17, 2011.

6. R.Uma, N.Murugesan, Asian Journal of Current Engineering and Maths 1: 6 NovDec (2012) 367 – 370.

7. Shariefuddin Pirzada and Ashay Dharwadker, Applications of Graph Theory, Journal of the korean society for industrial and applied mathematics, Vol.11, No. 4, 2007.

8. S Padmapriya, V.Sriram, B.Sooryanarayana, Edge odd gracefulness of the Wheel Graph, International Journal of Engineering Research and Technology Vol.2 (06), 2013,987-989

9. Vernold Vivin J, Venkatachalam M, Akbar Ali M.M.,Achromatic Coloring on Double Star Graph Families, International Journal of Mathematical Combinatorics Vol.3 (2009), 71-81