 Open Access
 Total Downloads : 279
 Authors : S Padmapriya, Dr. V. Sriram, Dr. B. Sooryanarayana
 Paper ID : IJERTV2IS60446
 Volume & Issue : Volume 02, Issue 06 (June 2013)
 Published (First Online): 12062013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
EdgeOdd Gracefulness of the Wheel Graph W _{1,n}
International Journal of Engineering Research & Technology (IJERT)
ISSN: 22780181
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 edgeodd graceful graph if there exists an injective map f : E(G)
{1,3,5,…,2q1} so that the induced map f + : V(G)
{0,1,2,3,…2k1} 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 edgeodd 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 edgeodd graceful graph if there exists an injective function f : E(G) {1,3,5,…,2q1} such that the
induced function f + : V(G) {0,1,2,3,…2k1}, 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 n1 and vnv1 are the rim edges.
Theorem 1.1. For a given integer n 4, the wheel graph W 1, n is edgeodd graceful.
Proof: Define a function f: E(W1,n): {1,3,…,4n1} depending upon n is even or odd as follows.
Case 1: n is odd
n+2j , if i = 0
f (vivj) = 4n+12i, if j = i+1 and 1 i (n1)/2 2n+12i, if j = i+1 and (n+1)/2 i n1 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 +(42i) mod 4n, if 1 i (n1)/2
2n+3 mod 4n, if i = (n+1)/2
n+(42i) 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+12i, if j = i+1and 1 i (n2)/2 2n+12i, if j = i+1 and n/2 i n1 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 +(52i) mod 4n, if 1 i (n2)/2 2n +5 mod 4n, if i = n/2
n + (52i) 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 3regular graph having 4 vertices and 6 edges. By the definition of edgeodd 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 edgeodd 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 edgeodd 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.
Case 1.1.12: {1,3,9},{3,7,11} and {1,5,11}.Nowthe 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 edgeodd graceful labelling for W1,3.
References

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

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, Edgeodd graceful labeling of some graphs, Electronics Notes in Discrete Mathematics, volume 33, April 2009, pp 1520.