International J.Math. Combin. Vol.

3(2012), 105-112

Odd Harmonious Labeling of Some Graphs

N.H.Shah
(Government Polytechnic, Rajkot - 360003, Gujarat, India) E-mail: [email protected], [email protected]

Abstract: The labeling of discrete structures is a potential area of research due to its
wide range of applications. The present work is focused on one such labeling called odd harmonious labeling. A graph G is said to be odd harmonious if there exist an injection f : V (G) {0, 1, 2, . . . , 2q 1} such that the induced function f : E (G) {1, 3, . . . , 2q 1} dened by f (uv ) = f (u) + f (v ) is a bijection. Here we investigate odd harmonious labeling of some graphs. We prove that the shadow graph and the splitting graph of bistar Bn,n are odd harmonious graphs. Moreover we show that the arbitrary supersubdivision of path Pn admits odd harmonious labeling. We also prove that the joint sum of two copies of cycle Cn for n 0(mod 4) and the graph Hn,n are odd harmonious graphs.

Key Words: Harmonious labeling, Smarandachely p-harmonious labeling, odd harmonious

AMS(2010): 05C78 1. Introduction We begin with simple, nite, connected and undirected graph G = (V (G), E (G)) with |V (G)| = p and |E (G)| = q . For standard terminology and notation we follow Gross and Yellen [5]. We will provide brief summary of denitions and other information which are necessary and useful for the present investigations. Denition 1.1 If the vertices are assigned values subject to certain condition(s) then it is known as graph labeling. Any graph labeling will have the following three common characteristics: (1) a set of numbers from which the vertex labels are chosen; (2) a rule that assigns a value to each edge; (3) a condition that these values must satisfy.
1 Received

April 5, 2012. Accepted September 18, 2012.

106

S.K.Vaidya and N.H.Shah

Graph labelings is an active area of research in graph theory which is mainly evolved through its rigorous applications in coding theory, communication networks, optimal circuits layouts and graph decomposition problems. According to Beineke and Hegde [1] graph labeling serves as a frontier between number theory and structure of graphs. For a dynamic survey of various graph labeling problems along with an extensive bibliography we refer to Gallian [2]. Denition 1.2 A function f is called graceful labeling of a graph G if f : V (G) {0, 1, 2, . . . , q } is injective and the induced function f : E (G) {1, 2, . . . , q } dened as f (e = uv ) = |f (u) f (v )| is bijective. A graph which admits graceful labeling is called a graceful graph. Rosa [8] called such a labeling a valuation and Golomb [3] subsequently called it graceful labeling. Several innite families of graceful as well as non-graceful graphs have been reported. The famous Ringel-Kotzig tree conjecture [7] and many illustrious works on graceful graphs brought a tide of dierent ways of labeling the elements of graph such as odd graceful labeling, harmonious labeling etc. Graham and Sloane [4] introduced harmonious labeling during their study of modular versions of additive bases problems stemming from error correcting codes. Denition 1.3 A graph G is said to be harmonious if there exist an injection f : V (G) Zq such that the induced function f : E (G) Zq dened by f (uv ) = (f (u) + f (v )) (mod q ) is a bijection and f is said to be harmonious labelling of G. If G is a tree or it has a component that is a tree, then exactly one label may be used on two vertices and the labeling function is not an injection. After this many researchers have studied harmonious labeling. A labeling is also introduced with minor variation in harmonious theme, which is dened as follows. Denition 1.4 Let k, p be integers with p 1 and k p. A graph G is said to be Smarandachely p-harmonious labeling if there exist an injection f : V (G) {0, 1, 2, . . . , kq 1} such that the induced function f : E (G) {1, p + 1, . . . , pq 1} dened by f (uv ) = f (u) + f (v ) is a bijection. Particularly, if p = k = 2, such a Smarandachely 2-harmonious labeling is called an odd harmonious labeling of G, f and f are called vertex function and edge function respectively. Liang and Bai [6] have obtained a necessary conditions for the existence of odd harmonious labelling of graph. It has been also shown that many graphs admit odd harmonious labeling and odd harmoniousness of graph is useful for the solution of undetermined equations. In the same paper many ways to construct an odd harmonious graph were reported. Vaidya and Shah [9] have also proved that the shadow and the splitting graphs of path Pn and star K1,n are odd harmonious graphs. Generally there are three types of problems that can be considered in this area. (1) How odd harmonious labeling is aected under various graph operations; (2) To construct new families of odd harmonious graph by investigating suitable function which generates labeling; (3) Given a graph theoretic property P, characterize the class/classes of graphs with prop-

Odd Harmonious Labeling of Some Graphs

107

erty P that are odd harmonious. The problems of second type are largely discussed while the problems of rst and third types are not so often but they are of great importance. The present work is aimed to discuss the problems of rst kind. Denition 1.5 The shadow graph D2 (G) of a connected graph G is constructed by taking two copies of G say G and G . Join each vertex u in G to the neighbours of the corresponding vertex v in G . Denition 1.6 For a graph G the splitting graph S (G) of a graph G is obtained by adding a new vertex v corresponding to each vertex v of G such that N (v ) = N (v ). Denition 1.7 The arbitrary supersubdivision of a graph G produces a new graph by replacing each edge of G by complete bipartite graph K2,mi (where mi is any positive integer) in such a way that the ends of each ei are merged with two vertices of 2-vertices part of K2,mi after removing the edge ei from the graph G. Denition 1.8 Consider two copies of a graph G and dene a new graph known as joint sum is the graph obtained by connecting a vertex of rst copy with a vertex of second copy. Denition 1.9 Hn,n is the graph with vertex set V (Hn,n ) = {v1 , v2 , , vn , u1 , u2 , , un } and the edge set E (Hn,n ) = {vi uj : 1 i n, n i + 1 j n}. 2. Main Results Theorem 2.1 D2 (Bn,n ) is an odd harmonious graph.
Proof Consider two copies of Bn,n . Let {u, v, ui , vi , 1 i n} and {u , v , u i , vi , 1 i n} be the corresponding vertex sets of each copy of Bn,n . Denote D2 (Bn,n ) as G. Then |V (G)| = 4(n + 1) and |E (G)| = 4(2n + 1). To dene f : V (G) {0, 1, 2, 3, . . . , 16n + 7}, we consider following two cases.

Case 1. n is even f (u) = 2, f (v ) = 1, f (u ) = 0, f (v ) = 5, f (ui ) = 9 + 4(i 1), 1 f (v1 ) = f (v2 ) = f (u n) f (u n) i n, f (u i ) = f (un ) + 4i, 1 i i
n 2

i
n 2,

n,

+ 3, f (v2i+1 ) = f (v1 ) + 8i, 1

f (v1 ) = f (vn ) + 6, f (v2 i+1 ) = f (v1 ) + 8i, 1

+ 5, f (v2i ) = f (v2 ) + 8(i 1), 2

1, 1,
n 2

i
n 2

f (v2 ) = f (vn ) + 8, f (v2 i ) = f (v2 ) + 8(i 1), 2

Case 2: n is odd

108

S.K.Vaidya and N.H.Shah

f (u) = 2, f (v ) = 1, f (u ) = 0, f (v ) = 5, f (ui ) = 9 + 4(i 1), 1 f (v1 ) = f (u n) i n, f (u i ) = f (un ) + 4i, 1 i i i n, + 3, f (v2i+1 ) = f (v1 ) + 8i, 1
n1 2 , 1 i n 2 , n1 2 , 1 i n 2

f (v2 ) = f (u n ) + 5, f (v2i ) = f (v2 ) + 8(i 1), 2

= f (vn ) + 8,

f (v2 i)

f (v2 )

+ 8(i 1), 2

The vertex function f dened above induces a bijective edge function f : E (G) {1, 3, . . . , 16n + 7}. Thus f is an odd harmonious labeling for G = D2 (Bn,n ). Hence G is an odd harmonious graph. Illustration 2.2 Odd harmonious labeling of the graph D2 (B5,5 ) is shown in Fig. 1.
u2 u1
9 17 13 21 3

u4 u5
25

v2 v1
48 50

3 56

v4
58

v5
64

u'
0

v'
5

29

45

66

82 72 74 80

u' 1

33

' u2

37

41

' u5

' u3

' u4

' v1

' v5

' v2

' v3

' v4

Fig. 1

Theorem 2.3 S (Bn,n ) is an odd harmonious graph. Proof Consider Bn,n with vertex set {u, v, ui , vi , 1 i n}, where ui , vi are pendant vertices. In order to obtain S (Bn,n ), add u , v , u i , vi vertices corresponding to u, v, ui , vi where, 1 i n. If G = S (Bn,n ) then |V (G)| = 4(n + 1) and |E (G)| = 6n + 3. We dene vertex labeling f : V (G) {0, 1, 2, 3, . . . , 12n + 5} as follows. f (u) = 0, f (v ) = 3, f (u ) = 2, f (v ) = 1, f (ui ) = 7 + 4(i 1), 1 f (vi+1 ) = f (v1 ) + 4i, 1 f (u 1) = f (vn ) + 5, i i n, f (v1 ) = f (un ) + 3, = f (u 1 ) + 2i, 1 n 1, i i n 1, n 1.

f (u i+1 )

f (v1 ) = f (u n ) 1, f (vi+1 ) = f (v1 ) + 2i, 1

Odd Harmonious Labeling of Some Graphs

109

The vertex function f dened above induces a bijective edge function f : E (G) {1, 3, , 12n + 5}. Thus f is an odd harmonious labeling of G = S (Bn,n ) and G is an odd harmonious graph. Illustration 2.4 Odd harmonious labeling of the graph S (B5,5 ) is shown in Fig. 2.

' u2 ' u1
47

' u3
51

' u4
53

' v2 ' u5
55

' v3
58

' v4
60

49

' v1
54

56

' v5
62

u u1
7

v v5

u2
11

u3
15

u4
19

23

26

v2
30

u5

v1

v3
34

v4
38

42

u'

v'

Fig. 2

Theorem 2.5 Arbitrary supersubdivision of path Pn is an odd harmonious graph. Proof Let Pn be the path with n vertices and vi (1 i n) be the vertices of Pn . Arbitrary supersubdivision of Pn is obtained by replacing every edge ei of Pn with K2,mi and we denote this graph by G. Let uij be the vertices of mi -vertices part of K2,mi where
n1

n 1 and 1

max{mi }. Let =

mi and q = 2. We dene vertex labeling

f : V (G) {0, 1, 2, 3, , 2q 1} as follows. f (vi+1 ) = 2i, 0 i n 1, j m1 , j mi , 2 i n.

f (u1j ) = 1 + 4(j 1), 1

f (uij ) = f (u(i1)n ) + 2 + 4(j 1), 1

The vertex function f dened above induces a bijective edge function f : E (G) {1, 3, , 2q 1}. Thus f is an odd harmonious labeling of G. Hence arbitrary supersubdivision of path Pn is an odd harmonious graph. Illustration 2.6 Odd harmonious labeling of arbitrary supersubdivision of path P5 is shown in Fig. 3.

110

S.K.Vaidya and N.H.Shah

u11
1

u31
21

u12

u21
15

u32
25

u41
39

v1
0

v2
2

v3
4

u33
29

v4
6

u42
43

v5
8

u13
9

u22
19

u34
33

u43
47

u14
13

u35
37

Fig. 3

Theorem 2.7 Joint sum of two copies of Cn admits an odd harmonious labeling for n 0(mod 4). Proof We denote the vertices of rst copy of Cn by v1 , v2 , . . . , vn and vertices of second copy by vn+1 , vn+2 , . . . , v2n . Join the two copies of Cn with a new edge and denote the resultant graph by G then |V (G)| = 2n and |E (G)| = 2n + 1. Without loss of generality we assume that the new edge by vn vn+1 and v1 , v2 , , vn ,vn+1 , vn+2 , . . . , v2n will form a spanning path in G. Dene f : V (G) {0, 1, 2, 3, , 4n + 1} as follows. f (v2i+1 ) = 2i, 0
n f v 32 +2i1 =

i
3n 2

3n 4

1, i

+ 2i, 1 i
n 4,

n 4,

f (v2i ) = 2i 1, 1 f vn = 2 +2i+2
n 2

+ 3 + 2i, 0

3n 4

1.

The vertex function f dened above induces a bijective edge function f : E (G) {1, 3, . . . , 4n + 1}. Thus f is an odd harmonious labeling of G. Hence joint sum of two copies of Cn admits odd harmonious labeling for n 0(mod 4). Illustration 2.8 Odd harmonious labeling of the joint sum of two copies of C12 is shown in Fig. 4.
13 10 12 0 25

v11
11

v12

v1 v2
1 24

v24 v23

v13

15

v14 v15 14 v16 v17 16

v10

v9
9

v3 v4 v7
6 3

23

v22

v8 v6
5

v 22 21 v20
21

v5
4

v19
20

v18
19

Fig. 4

Theorem 2.9 The graph Hn,n is on odd harmonious graph.

Odd Harmonious Labeling of Some Graphs

111

Let V = {v1 , v2 , , vn }, U = {u1 , u2 , , un } be the partition of V (Hn,n ). Let n(n + 1) G = Hn,n then |V (G)| = 2n and |E (G)| = . We dene odd harmonious labeling 2 2 f : V (G) {0, 1, 2, 3, , (n + n 1)} as follows. Proof f (vi ) = i(i 1), 1 i n, i n.

f (ui ) = (2n + 1) 2i, 1

The vertex function f dened above induces a bijective edge function f : E (G) {1, 3, , n2 + n 1 . Thus f is an odd harmonious labeling of G. Hence the graph Hn,n is on odd harmonious graph. Illustration 2.10 Odd harmonious labeling of the graph H5,5 is shown in Fig. 5.
v1
0

v2
2

v3
6

v4
12

v5
20

u5

u4

u3

u2

u1

Fig. 5.

3. Concluding Remarks Liang and Bai have proved that Pn , Bn,n are odd harmonious graphs for all n and Cn is odd harmonious graph for n 0(mod 4) while we proved that the shadow and the splitting graphs of Bn,n admit odd harmonious labeling. Thus odd harmoniousness remains invariant for the shadow graph and splitting graph of Bn,n . It is also invariant under arbitrary supersubdivision of Pn . To investigate similar results for other graph families and in the context of various graph labeling problems is a potential area of research. Acknowledgement The authors are thankful to the anonymous referee for valuable comments and kind suggestions.

References [1] L.W.Beineke and S.M.Hegde, Strongly multiplicative graphs, Discuss. Math. Graph Theory , 21(2001), 63-75. [2] J.A.Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, 18(2011) #DS 6, Available also online: http://www.combinatorics.org/Surveys/ds6.pdf. [3] S.W.Golomb, How to number a graph, in Graph Theory and Computing R C Read, ed., Academic Press, New York (1972), 23-37.

112

S.K.Vaidya and N.H.Shah

[4] R.L.Graham and N.J. A.Sloane, On additive bases and harmonious graphs, SIAM J. Algebr. Disc. Meth., 1(4)(1980), 382-404. [5] J.Gross and J.Yellen, Graph Theory and Its Applications, CRC Press, 1999. [6] Z.Liang and Z.Bai, On the odd harmonious graphs with applications, J. Appl. Math. Comput. 29(2009), 105-116. [7] G.Ringel, Problem 25, Theory of graphs and its applications, Proc. of Symposium Smolenice 1963, Prague, (1964), 162. [8] A.Rosa, On certain valuations of the vertices of a graph, Theory of graphs, International Symposium, Rome, July (1966), Gordon and Breach, New York and Dunod Paris(1967), 349-355. [9] S.K.Vaidya and N.H.Shah, Some new odd harmonious graphs, International Journal of Mathematics and Soft Computing, 1(2011), 9-16, Available also online: http://www.ijmsc. com/index.php/ijmsc.