Edge-Odd Gracefulness of the Wheel Graph W _1,n

Edge-Odd Gracefulness of the Wheel Graph W _1,n

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 2 Issue 6, June – 2013

S Padmapriya , Dr. V. Sriram, Dr. B. Sooryanarayana , Department of Mathematics, Department of Mathematics, Department of Mathematical and Sir M Visvesvaraya Institute Alliance College of Engineering Computational Studies,

of Technology, and Design, Dr.Ambedkar Institute Of

Bangalore, India Bangalore, India Technology, Bangalore, India

Abstract

A (p,q)- connected graph is an edge-odd graceful graph if there exists an injective map f : E(G)

{1,3,5,…,2q-1} so that the induced map 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} makes all edges distinct and odd. In this paper the edge-odd gracefulness of the wheel graph W 1,n is obtained for n 4.

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

AMS Classification Number: 05C78

1. Introduction

All the graphs considered in this paper are simple, undirected, finite and connected. The terms not defined here may be found in [1]. A vertex labelling of a graph G is a function f : V(G) Z+. An injective vertex labelling f : V(G) {0,1,2,…,|E(G)|} is called graceful labelling if the induced function f + : E(G) Z+, defined by f(uv) = | f(u) f(v)|, is injective.[2]

A (p,q)- connected graph 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 injective.[3][4]

The sum of two graphs G1 and G2, denoted by G1 + G2, is defined as a graph G whose vertex set is V(G1) U V(G2) and the edge set is E(G1) U E(G2) U { xy : x V(G1), y V(G2)}. A wheel W 1,n is a graph Cn + K1. Further the vertices of Cn in W1,n are called its rim vertices and the vertex of K1 is called its centre. An edge in a wheel which joins a rim vertex to the centre is called its spoke. Throughout this paper, we denote

the centre of a wheel W1,n by v0 and the rim vertices by v1,v2,v3,…vn, so that the edges v0vi , 1 i n are the spoke edges and vivi+1 , 1 i n-1 and vnv1 are the rim edges.

Theorem 1.1. For a given integer n 4, the wheel graph W 1, n is edge-odd graceful.

Proof: Define a function f: E(W1,n): {1,3,…,4n-1} depending upon n is even or odd as follows.

Case 1: n is odd

n+2j , if i = 0

f (vivj) = 4n+1-2i, if j = i+1 and 1 i (n-1)/2 2n+1-2i, if j = i+1 and (n+1)/2 i n-1 1, if i = n, j = 1

By the definition of f as in the above, it follows that 3n mod4n, if i = 0

f +(vi) = n +(4-2i) mod 4n, if 1 i (n-1)/2

2n+3 mod 4n, if i = (n+1)/2

n+(4-2i) mod 4n, if (n+3)/2 i n

Since n 4 we have 4 – 2i 2 and even, 2n 8 and hence it is clear that f +(vi) f +(vj) whenever i j.

Case 2: n is even

n+2j+1, if i = 0

f (vivj)= 4n+1-2i, if j = i+1and 1 i (n-2)/2 2n+1-2i, if j = i+1 and n/2 i n-1 1, if i = n and j = 1

By the definition of f as in the above, it follows that

2n mod 4n, if i = 0

f +(vi) = n +(5-2i) mod 4n, if 1 i (n-2)/2 2n +5 mod 4n, if i = n/2

n + (5-2i) mod 4n, if (n+2)/2 i n Since n 4 we have 5 – 2i 3 and odd, 2n 8 and hence it is clear that f +(vi) f +(vj ) whenever i j. Thus f is an edge odd graceful labelling for any n 4.

Theorem 1.2. The connected graph W 1,3

K4 is not edge odd graceful.

Proof: Since W1,3 is a 3-regular graph having 4 vertices and 6 edges. By the definition of edge-odd graceful labelling, each edge of W1,3 can take only one of the label in {1,3,5,7,9,11}. Again by definition of edge-odd graceful labelling we should have a unique label at each vertex whose value is the sum of the edge labels incident at it under modulo 12 in case of W1,3. Since each vertex is of degree 3, the only possible sums with three numbers are given below. Let the sum of the edge labels {a,b,c} incident at a vertex be denoted by S.

case 1: S = 1

{1,3,9},{1,5,7}and {5,9,11}

case 2: S = 3

{1,3,11},{1,5,9},{3,5,7}and {7,9,11}

case 3: S = 5

{1,5,11},{1,7,9}and {3,5,9}

case 4: S = 7

{1,7,11},{3,5,11}and {3,7,9}

case 5: S = 9

{1,3,5},{3,7,11}and {5,7,9}

case 6: S = 11

{1,3,7},{3,9,11}and {5,7,11}

Now for a wheel W1,3 an edge-odd graceful labelling exists, then we must be able to get 4 such sets from the above sets such that each set is from one of the cases above and the intersection between the sets is exactly at one number and that number is appearing only in those two sets.

Now w.l.o.g. let one of the vertices has the sum S = 1, then we have the following cases.

Case 1.1.1: {1,3,9},{3,5,7} and {1,5,11}.Now the

last set is now forced to be as {7,9,11}. Then both

{7,9,11} and {3,5,7} are from case 2, which is a contradiction to the fact that there should be only one set from each case. Otherwise it violates the condition that there should be unique label at each vertex.

Case 1.1.2: {1,3,9},{3,5,7} and {1,7,11}.Now the

last set is now forced to be as {5,9,11}. Then both

{1,3,9} and {5,9,11} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.3: {1,3,9},{7,9,11} and {1,5,11}.Now the

last set is now forced to be as {3,5,7}. Then both

{3,5,7} and {7,9,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.4: {1,3,9},{7,9,11} and {3,5,11}.Now the

last set is now forced to be as {1,5,7}. Then both

{1,5,7} and {1,3,9} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.5: {1,3,9},{1,5,11} and {3,5,7}.Now the

last set is now forced to be as {7,9,11}. Then both

{3,5,7} and {7,9,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.6: {1,3,9},{1,5,11} and {7,9,11}.Now the

last set is now forced to be as {3,5,7}. Then both

{3,5,7} and {7,9,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.7: {1,3,9},{1,5,11} and {3,7,11}.Now the

last set is now forced to be as {5,9,7}. Then both

{5,9,7} and {3,7,11} are from case 5, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.8: {1,3,9},{1,7,11} and {3,5,7}.Now the

last set is now forced to be as {5,9,11}. Then both

{5,9,11} and {1,3,9} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.9: {1,3,9},{1,7,11} and {5,7,9}.Now the

last set is now forced to be as {3,5,11}. Then both

{1,7,11} and {3,5,11} are from case 4, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.10: {1,3,9},{3,5,11} and {7,9,11}.Now

the last set is now forced to be as {1,5,7}. Then both {1,5,7} and {1,3,9} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.1.11: {1,3,9},{3,5,11} and {5,7,9}.Now the

last set is now forced to be as {1,7,11}. Then both

{1,7,11} and {3,5,11} are from case 4, which is a contradiction to the fact that there should be only one set from each case.

the last set is now forced to be as {5,7,9}. Then both {5,7,9} and {3,7,11} are from case 5, which is a contradiction to the fact that there should be only one set from each case.

Case 1.2.1: {1,5,7},{1,3,11} and {3,5,9}.Now the

last set is now forced to be as {7,9,11}. Then both

{7,9,11} and {1,3,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.2.2: {1,5,7},{1,3,11} and {3,7,9}.Now the

last set is now forced to be as {5,9,11}. Then both

{5,9,11} {1,5,7} and are from case 1, which is a

contradiction to the fact that there should be only one set from each case.

Case 1.2.3: {1,5,7},{7,9,11} and {3,5,9}.Now the

last set is now forced to be as {1,3,11}. Then both

{1,3,11} and {7,9,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.2.4: {1,5,7},{7,9,11} and {3,5,11}.Now the

last set is now forced to be as {1,3,9}. Then both

{1,3,9} and {1,5,7} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.1: {5,9,11},{1,3,11} and {1,7,9}.Now the

last set is now forced to be as {3,5,7}. Then both

{1,3,11} and {3,5,7} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.2: {5,9,11},{1,3,11} and {3,7,9}.Now the

last set is now forced to be as {1,5,7}. Then both

{1,5,7} and {5,9,11} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.3: {5,9,11},{3,5,7} and {1,7,9}.Now the

last set is now forced to be as {1,3,11}. Then both

{1,3,11} and {3,5,7} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.4: {5,9,11},{3,5,7} and {1,7,11}.Now the

last set is now forced to be as {1,3,9}. Then both

{1,3,9} and {5,9,11} are from case 1, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.5: {5,9,11},{1,7,9} and {1,3,5}.Now the

last set is now forced to be as {3,7,11}. Then both

{3,7,11} and {1,3,5} are from case 5, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.6: {5,9,11},{3,7,9} and {1,3,5}.Now the

last set is now forced to be as {1,7,11}. Then both

{1,7,11} and {3,7,9} are from case 4, which is a contradiction to the fact that there should be only one set from each case.

Case 1.3.7: {5,9,11},{1,7,11} and {1,3,5}.Now the

last set is now forced to be as {3,7,9}. Then both

{3,7,9} and {1,7,11} are from case 4, which is a contradiction to the fact that there should be only one set from each case.

From the above cases we can conclude that a vertex with sum S = 1 is never possible. Therefore case 1 is eliminated.

Now we use case 3.

Case 3.1.1: {1,5,11},{3,5,7} and {3,9,11}. Now the

last set is forced to be as {1,7,9}. Then both

{1,7,9} and {1,5,11} are from case 3, which is a contradiction to the fact that there should be only one set from each case.

Case 3.1.2: {1,5,11},{7,9,11} and {1,3,7}. Now the

last set is forced to be as {3,5,9}. Then both

{1,5,11} and {3,5,9} are from case 3, which is a contradiction to the fact that there should be only one set from each case.

Case 3.1.3: {1,5,11},{5,7,9} and {1,3,7}. Now the

last set is forced to be as {3,9,11}. Then both

{3,9,11} and {1,3,7} are from case 6, which is a contradiction to the fact that there should be only one set from each case.

There exists no unique pattern different from the previously known patterns. Therefore no correct pattern containing the set {1,7,9} exists.

There exists no unique pattern different from the previously known patterns. Therefore no correct pattern containing the set {3,5,9} exists.

From the above cases we can conclude that a vertex with sum S = 5 is never possible. Therefore case 3 is eliminated.

Now we use case 4.

Case 4.1.1: {1,7,11},{1,5,9} and {3,9,11}. Now the

last set is forced to be as {3,5,7}. Then both

{3,5,7} and {1,5,9} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 4.2.1: {3,5,11},{1,5,9} and {1,3,7}. Now the

last set is forced to be as {7,9,11}. Then both

{1,5,9} and {7,9,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

Case 4.3.1: {3,7,9},{1,3,11} and {5,7,11}. Now the

last set is forced to be as {1,5,9}. Then both

{1,5,9} and {1,3,11} are from case 2, which is a contradiction to the fact that there should be only one set from each case.

From the above cases, we can conclude that a vertex with sum S = 7 is never possible. Therefore case 4 is eliminated.

Remaining sums are only in 3 cases which are not sufficient to label 4 vertices which is a contradiction.

Therefore there exists no edge-odd graceful labelling for W1,3.

References

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

2. Joseph A. Gallian, A Dynamic Survey of Graph Labeling, the electronic journal of combinatorics 17 (2010), #DS6, Thirteenth edition, November 13, 2010. [3]A.Solairaju and A.Sathik Batcha, Edge odd gracefulness of Halin graphs of types H(4,n) and H(5,n), International Journal of Open Problems in Mathematics and Applications, Volume 1, No.1, March 2011. [4]A.Solairaju and K.Chitra, Edge-odd graceful labeling of some graphs, Electronics Notes in Discrete Mathematics, volume 33, April 2009, pp 15-20.