Graceful Labeling Of A Tree With Hanging Stars Biology Essay

Published:

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)}

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.