Graceful Labeling Of A Tree With Hanging Stars Biology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract: In this paper, it is shown graceful a labeling of special type of tree obtained from a family of n stars having number of branches of those stars form an arithmetic progression with common difference k and one of the branches of each of those stars merged with one different point successively in a common path on n vertices.

Key words: graceful labeling, supporting vertices, hanging vertices, free leaves, growing stars, common difference.

Mathematics subject classification 2010: 05C78

INTRODUCTION

A graph G with p vertices and q edges, vertex set V(G) and edge set E(G) is said to be graceful labeling if the bijection f:V(G)→{0, 1, … , q}such that :{u, v} is an edge in G ={1,2… q}is the edge set E(G). All the edge values are distinct.

Gallian, J A [5] gives extensive survey on graceful labeling. C. Huang, A. Kotzig, and A. Rosa [2] gives a new class of graceful trees, G. Sethuraman and J. Jesintha [3] shows a new class of graceful rooted trees, they showed generating new graceful trees[4] and B. D. Acharya, S. B. Rao, and S. Arumugan[1] given ideas graceful labeling of graphs.

The tree with n hanging stars whose number of branches are in arithmetic progression with (step k) common difference k having one of the branch points in each of those stars is merged with a point in a common path on n vertices as support points of those stars respectively.

Main results

Let S1, S2 . . . Sn be stars with = i for i = 1, 2, 3 . . . n. Let the support points of the hanging stars S1, S2, . . . Sn be s1, s2, s3, …, sn respectively and denote the free leaves of each of the stars Si by f1(i), f2(i), …. fi-1(i) for i = 1, 2 … n.

Let c1, c2…, cn be the central vertices of the stars S1, S2, S3 … Sn respectively.

A tree with growing n hanging stars as branches whose cardinality are in arithmetic progression with common difference 1 (step 1) is denoted

It can be verified that the number of vertices of can be recursively defined by the relation

Also the edges of can be defined by the relation

,

Because of the above relation, we define the relation between two successive trees and as

,

where - denote the difference between the number of vertices (edges) of and .

A general tree drawn in figure 1.

Figure 1

We also denote the labeling of node v in the tree as l (v). Here, for the tree , we assign the labeling as follows in six groups.

R (1): l (s1) = 0; l (c1) = q; l (c2) = 1 and l (s2) = q-1.

R (2): l (s2m+1) = l (s2m-1) + (2m + 1), m ≥ 1.

R (3): l (s2m +2) = l (s2m) - (2m + 2), m ≥ 1.

R (4): l (c2m + 1) = l (c2m-1) - (2m +1), m ≥ 1.

R (5): l (c2m + 2) = l (c2m) + (2m + 2), m ≥ 1.

Let the free leaves of growing mth star of at sm be f1m, f2m….

Then for m ≥ 1

The labeling of free leaves of odd stars of S2m+1 based on its supporting vertex s2m+1 as follows.

R (6) a: labeling of free leaves of S2m + 1 is the set of integers {l (s2m + 1) ± 1, l (s2m +1) ± 2) … l (s2m +1) ± m}

The labeling of free leaves of even stars of S2m based on its supporting vertex s2m as follows.

R(6)b: labeling of free leaves of S2m is the set of integers { l(s2m ) ± 1, l(s2m ) ± 2, . . ., l(s2m ) ± (m-1), l(s2m ) - m}

From the above labeling, we observe that the relation between labeling of supporting vertices and center vertices of hanging stars that are given below.

l (s2m + 1) = l (c2m) + (m +1), m ≥ 1.

l (s2m + 2) = l (c2m + 1) - (m + 1), m ≥ 0.

From the above labeling procedure we observe that the excess vertices of

over are labeled in terms of labeling of as follows recursively.

Relation table 1:

Vertices of last branch of present tree

Relation

Vertices of last branch of previous tree

Supporting vertex l(s2m+1)

=

l(s2m)

Central vertex l(c2m+1)

=

l(c2m) + (2m +2)

Leaves of S2m+1

=

The set{,…,} ∪{successor of maximum integer value in the above set}

Table 1

Relation table 2:

Vertices of last branch of present tree

Relation

Vertices of last branch of previous tree

Supporting vertex l(s2m)

=

l(s2m-1) +(2m + 1)

Central vertex l(c2m)

=

l(c2m-1)

Leaves of S2m

=

The set {+ (2m +1), + (2m + 1)…,+ (2m + 1)} ∪{l(c2m-1) + 1}

Table 2

The above labeling of vertices induces a bijective mapping gV and gE as follows

gE: E () → {1, 2, 3…,}

and

gV: → {0, 1, 2…,},

which could be easily verified easily that it is a graceful labeling for a given tree

from the following assignment tables.

Edge assignment of by the relation {1, 2, 3…,} is given as follows.

Assignment table 1:

Tn

2

3

4

5

6

n

Edge s1c1

4

8

13

19

26

q

Edge s1s2

3

7

12

18

25

q-1

Edge s2c2

2

6

11

17

24

q-2

Remaining free leaves of S2

1

5

10

16

23

q-3

Edge s2s3

4

9

15

22

q-4

Edge s3c3

---

3

8

14

21

q-5

Remaining free leaves of S3

--

2,1

7,6

13,12

20,19

q-6,q-7

Edge s3s4

--

5

11

18

q-8

Edge s4c4

--

4

10

17

q-9

Remaining free leaves of S4

---

3 to 1

9 to 7

16 to 14

q-10 to q-12

Edge s4s5

--

6

13

q-13

Edge s5c5

--

5

12

q-14

Remaining free leaves of S5

--

4 to 1

11 to 8

q-15 to q-18

Edge s5s6

--

7

Etc.(common

difference is 1)

Edge s6c6

--

6

Remaining free leaves of S6

---

5 to 1

Table 3

The vertex assignment of as follows

Assignment table 2:

Tn

2

3

4

5

6

n=i

s1

0

0

0

0

0

0

c1

4

8

13

19

26

q

s2

3

7

12

18

25

q-1

c2

1

1

1

1

1

1

of S2

2

6

11

17

24

q-2

s3

--

3

3

3

3

3

c3

---

5

10

16

23

q-3

of S3

--

2,4

2,4

2,4

2,4

2, 4

s4

--

--

8

14

21

q-5

c4

--

---

5

5

5

5

of S4

---

---

6,7,9

12,13,15

19,20,22

{(q-4) to (q-7)except (q-5)}

s5

--

---

---

8

8

8

c5

--

---

--

11

18

q-8

of S5

--

---

---

6,7,9,10

6,7,9,10

6,7,9,10

s6

--

---

---

----

15

q-11

c6

--

---

---

---

11

11

of S6

---

---

---

----

12,13,14,16,17

{(q-9) to (q-14) except (q-10)}

The general form of as follows. (replace q by p remains same)

We also observe this scheme can be extended to graceful labeling of

for k = 2, 3, 4 … with following assignments to vertices.

Assuming the common difference k, the stars are k, 2k, 3k… in ascending order. The following table gives ready reference for any difference k.

vertex assignment as follows.

Tn

n=k

s1

0

c1

q

s2

q-1

c2

1

of S2

{q-2 to (q-1-k)}

s3

k+2

c3

q-2-k

of S3

{2 to (2k+2)except(k+2)}

s4

q-3-2k

c4

2k+3

of S4

{(q-3-k) to (q-3-4k)except (q-3-2k)}

s5

4k+4

c5

q-4k-4

of S5

{(2k+4) to (6k+4) except (4k+4)}

s6

q-5-6k

c6

6k+5

of S6

{(q-5-4k) to (q-5-9k) except (q-5-5k)}