# Harmonious Properties of Uniformk-Distant Trees

Authors: M. Murugan
Journal: Chinese Journal of Mathematics
 (2013)

---

## Abstract

We prove that all uniformk-distant trees are harmonious; every uniform k-distant odd tree is strongly c-harmonious, so is every uniform k-distant even tree if the spine has even number of vertices. Also, all uniform k-distant trees are sequential.


---

## Body

## 1. Introduction

Labeling of a graph is an assignment of labels (numbers) to its vertices or/and edges or faces, which satisfy some conditions. These are different from coloring problems since some properties and structures of numbers such as ordering, addition, and subtraction used here are not properties of colors. Graph labelings have several applications in many fields. They have found usage in various coding theory problems, including the design of good radar-type codes, synch-set codes, and convolutional codes with optimal autocorrelation properties. They facilitate the optimal nonstandard encodings of integers. They have also been applied to determine ambiguities in X-ray crystallographic analysis, to design of a communication network addressing system, to determine optimal circuit layouts, and to problems in additive number theory.Graham and Sloane [1] have introduced harmonious graphs in their study of modular versions of additive bases problems stemming from error-correcting codes. The conjecture “All Trees are Harmonious” is still open and is unsettled for many years. Gallian in his survey [2] of graph labeling has mentioned that no attention has been given to analyze the harmonious property of lobsters. It is clear that uniform 2-distant trees are special lobsters. Murugan [3] has proved that uniform k-distant trees are graceful and have many interesting properties. Also, Abueida and Roberts [4] have proved that uniform k-distant trees admit a harmonious labeling, when they have even number of vertices. In this paper, we prove that all uniform k-distant trees are harmonious; and every uniform k-distant odd tree is strongly c-harmonious; every uniform k-distant even tree is strongly c-harmonious, when the spine has even number of vertices. Also, all uniform k-distant trees are sequential.


## 2.k-Distant Tree

Ak-distant tree consists of a main path called the “spine,” such that each vertex on the spine is joined by an edge to at most one path on k-vertices. Those paths are called “tails” (i.e., each tail must be incident with a vertex on the spine). When every vertex on the spine has exactly one incident tail of length k, we call the tree a uniformk-distant tree.A uniformk-distant tree with odd number of vertices is called a uniform k-distant odd tree. A uniform k-distant tree with even number of vertices is called a uniform k-distant even tree.To prove our results, we name the vertices of anyuniformk-distant tree as in Figure 2 with the help of Figure 1. The arrows on Figure 1 show the order of naming the vertices.Figure 1
Order to name the vertices.Figure 2
Uniformk-distant tree.


## 3. Variations of Harmonious Labelings

In this section, we list a few existing labelings which are useful for the development of this paper. Here, we consider a graphG with p vertices and q edges.Definition 1 (harmonious labeling).
An injective functionf from the vertices of G to the group of integers modulo q, the number of edges, is called harmonious if all edge labels are distinct when each edge xy is assigned the label f(x)+f(y) (mod q); when G is a tree, exactly one label may be used on two vertices.
This was introduced by Graham and Sloane [1].Definition 2 (harmonious graph).
A graph which has a harmonious labeling is called a harmonious graph.Definition 3 (stronglyc-harmonious labeling).
An injective functionf of a graph G is strongly c-harmonious if the vertex labels are from {0,1,…,q-1} and the edge labels induced by f(x)+f(y) for each edge xy are c,…,c+q-1; when G is a tree, exactly one label may be used on two vertices.
This was introduced by Chang et al. [5].Definition 4 (stronglyc-harmonious graph).
A graph which has a stronglyc-harmonious labeling is called a strongly c-harmonious graph.Definition 5 (sequential labeling).
An injective functionf of a graph G is sequential if the vertex labels are from {0,1,…,q-1} and the edge labels induced by f(x)+f(y) for each edge xy are c,…,c+q-1; when G is a tree, the vertex labels are from {0,1,…,q} with no vertex label being used twice.
This was introduced by Grace [6].Definition 6 (sequential graph).
A graph which has a sequential labeling is called a sequential graph.


## 4. Results

Theorem 7.
Every uniformk-distant tree is harmonious.Proof.
LetT be a uniform k-distant tree T with p vertices and q edges. Since it is a tree, q=p-1.
To proveT is harmonious, we need a labeling f from the vertices of G to the group of integers modulo q such that all the edge labels are distinct, when each edge xy is assigned the label f(x)+f(y) (mod q); since T is a tree, one label, say 0, may be used on two vertices. So, we can take the codomain of f to be {0,1,2,…,q}.
Define a labelingf from V(T) into {0,1,2,…,q} such that
(1)f(vi)=(i-1)2,ifiisodd=⌈p2⌉+(i2-1),ifiiseven.
We note that the sum of the labels of two consecutive vertices of the spine (i.e., labels on the edges of the spine) is equal to the sum of the labels at the end vertices of the corresponding tail (e.g., sum of the labels at vn and vn+1 is equal to sum of the labels at v1 and v2n), by construction and labeling.
Case
1 (
p
is even). The odd vertices v1,v3,…,vp-1 receive the labels 0,1,2,…,(p/2)-1, respectively. The even vertices v2,v4,…,vp receive the labels (p/2),(p/2)+1,…,p-1, respectively. Therefore, the edges receive the labels  (p/2),(p/2)+1,(p/2)+2,…,(p/2)-1+p-1=(p/2)+q-1.
That is, the edges receive the labels(p/2),(p/2)+1,(p/2)+2,…,(p/2)+q-1.
That is, the edges receive the labels(p/2),(p/2)+1,…,(p/2)+((p/2)-1),(p/2)+(p/2),(p/2)+((p/2)+1),…,(p/2)+q-1.
That is, the edges receive the labels(p/2),(p/2)+1,…,p-1,p,p+1,…,(p/2)+q-1.
That is, the edges receive the labels((q+1)/2),((q+3)/2),…,q-1,q,q+1,q+2,…,((3q-1)/2).
That is, the edges receive the labels((q+1)/2),((q+3)/2),…,q-1,0,1,2,…,((q-1)/2) under addition modulo q.
That is, the edges receive the labels0,1,2,…,q-1.
Hence,T is harmonious.
Case
2 (
p
is odd). The odd vertices v1,v3,…,vp receive the labels 0,1,2,…,((p-1)/2), respectively. The even vertices v2,v4,…,vp-1 receive the label,
(2)⌈p2⌉,⌈p2⌉+1,…,⌈p2⌉+p-12-1=p-1,respectively.
Therefore, the edges receive the labels
(3)⌈p2⌉,⌈p2⌉+1,⌈p2⌉+2,…,p-1+p-12=p-12+q=p+12+q-1=⌈p2⌉+q-1.
That is,
(4)⌈p2⌉,⌈p2⌉+1,⌈p2⌉+2,…,⌈p2⌉+q-1.
As in Case 1, this is nothing but 0,1,2,…,q-1.
Hence,T is harmonious.Theorem 8.
Every uniformk-distant odd tree is strongly c-harmonious.Proof.
LetT be a uniform k-distant tree T with p vertices and q edges. Since it is a tree, q=p-1.
Define a labelingf from V(T) into {0,1,2,…,q-1} such that
(5)f(vi)=(i-1)2,ifiisodd=p-12+i2,ifiisevenandi≠p-1=0,ifi=p-1.
We note that the sum of the labels of two consecutive vertices of the spine (i.e., labels on the edges of the spine) is equal to the sum of the labels at the end vertices of the corresponding tail (e.g., sum of the labels at vn and vn+1 is equal to sum of the labels at v1 and v2n), by construction and labeling.
The odd verticesv1,v3,…,vp-2,vp receive the labels. 0,1,2,…,((p-3)/2),((p-1)/2), respectively. The even vertices v2,v4,…,vp-3 receive the labels ((p-1)/2)+1, ((p-1)/2)+2,…,p-2, respectively, and vp-1 receives the label 0. Therefore, the edges receive the labels
(6)p-12+1,p-12+2,p-12+3,p-12+4,…,p-2+p-32,p-32,p-12.
That is, the edges receive the labels ((p-1)/2)+1,((p-1)/2)+2,((p-1)/2)+3,…,((p-1)/2)+p-3,((p-1)/2)-1,((p-1)/2).
That is, the edge labels are((p-1)/2)-1,((p-1)/2),((p-1)/2)+1,((p-1)/2)+2,((p-1)/2)+3,…,((p-1)/2)+p-3.
That is,T is strongly (((p-1)/2)-1)-harmonious.Theorem 9.
Every uniformk-distant even tree with the spine having even number of vertices is strongly c-harmonious.Proof.
LetT be a uniform k-distant tree T with p vertices and q edges. Since it is a tree, q=p-1.
Define a labelingf from V(T) into {0,1,2,…,q-1} such that
(7)f(vi)=(i-1)2,ifiisodd=p2+i2-1,ifiisevenandi≠p=0,ifi=p.
We note that the sum of the labels of two consecutive vertices of the spine (i.e., labels on the edges of the spine) is equal to the sum of the labels at the end vertices of the corresponding tail (e.g., sum of the labels at vn and vn+1 is equal to sum of the labels at v1 and v2n), by construction and labeling.
The odd verticesv1,v3,…,vp-1 receive the labels 0,1,2,…,(p/2)-1, respectively. The even vertices v2,v4,…,vp-2 receive the labels (p/2),(p/2)+1,…,p-2, respectively and vp receives the label 0. Therefore, the edges receive the labels
(8)p2,p2+1,p2+2,…,p+p2-3,p2-1.
That is, the edge labels are (p/2)-1,(p/2),(p/2)+1,(p/2)+2,…,p+(p/2)-3.
That is,T is strongly ((p/2)-1)-harmonious.Theorem 10.
Every uniformk-distant tree is sequential.Proof.
LetT be a uniform k-distant tree T with p vertices and q edges. Since it is a tree, q=p-1.
Define a labelingf from V(T) into {0,1,2,…,q} such that
(9)f(vi)=(i-1)2,ifiisodd=⌈p2⌉+(i2-1),ifiiseven.
The rest is routine verification. Hence, T is sequential.



---

*Source: 725451-2013-11-05.xml*