1. Introduction
All graphs considered here are simple, finite, connected and undirected. We follow the basic notations and terminologies of graph theory as in [1]. The symbols
and
denote the vertex set and the edge set of a graph G. Let
be a graph with
vertices and
edges. A labeling f of a graph G is a mapping that assigns elements of a graph to the set of numbers (usually to positive or non-negative integers). If the domain of the mapping is the set of vertices (the set of edges) then we call the labeling vertex labeling (edge labeling). The labels of the vertices induce labels of the edges. There are several types of labeling. A detailed survey of graph labeling can be found in [2]. A vertex labeling f is said to be difference labeling if it induces the label
for each edge xy which is called as weight of the edge xy.
A difference labeling f of a graph G is said to be k-equitable if for each weight induced by f on the edges of G appears exactly k times. If a graph G has a k-equitable labeling then G is said to be k-equitable. Equitable labeling of graphs was introduced by Bloom and Ruiz in [3]. A brief summary of definitions which are useful for the present study is given below.
Definition 1.1 [4] Let T be a tree and u0 and
be two adjacent vertices in T. Let u and v be two pendant vertices of T such that the length of the path u0-u is equal to the length of the path
-v. If the edge
is deleted from T and u and v are joined by an edge uv, then such a transformation of T is called an elementary parallel transformation (or an ept, for short) and the edge
is called transformable edge.
If by a sequence of ept’s, T can be reduced to a path, then T is called a Tp tree (transformed tree) and such sequence is regarded as a composition of mappings (ept’s) denoted by P, is called a parallel transformation of T. The path, the image of T under P is denoted as P(T).
A Tp tree and a sequence of two ept’s reducing it to a path are illustrated in Figure 1.
Definition 1.2 The corona
of the graphs G1 and G2 is obtained by taking one copy of G1 (with p vertices) and p copies of G2 and then joining the
vertex of G1 to every vertex of the
copy of G2.
Definition 1.3 Caterpillar is a tree with the property that the removal of its pendant vertices leaves a path.
Definition 1.4 The square graph G2 of a graph G has the vertex set
with
adjacent in G2 whenever
in G.
denotes the smallest integer greater than or equal to x.
The concept of mean labeling was introduced by S. Somasundaram and R. Ponraj in [5] and further studied in [6-8]. A. Lourdusamy and M. Seenivasan introduced a vertex equitable labeling in [9]. In a vertex equitable labeling we use the labels
for the vertices,
![](https://www.scirp.org/html/2-1200055\05f57ae0-6e0e-479b-8a36-1ecb71de1d86.jpg)
Figure 1. A Tp-tree and a sequence of two ept’s reducing it to a path.
the number of times the different vertex labels appear cannot differ by more than one. The induced edge labels are defined as the sum of the incident vertex labels. They proved that the graphs like path, bistar
combs
bipartite complete
friendship graph
for
quadrilateral snake,
if and only if
ladder graph
arbitrary super division of a path and cycle
with
or
are vertex equitable. Also they proved that the graph
if
Eulerian graph with n edges where
or
the wheel
the complete graph
if
and triangular cactus with q edges where
or 6 or 9
are not vertex equitable. Moreover they proved that if G is a graph with p vertices and q edges, q is even and
then G is not vertex equitable.
Definition 1.5 [9] Suppose G is a graph with p vertices and q edges. Let
A vertex labeling
induces an edge labeling
defined by
for all edges uv. For
let
be the number of vertices v with
A graph G is vertex equitable if there exists a vertex labeling f such that for all a and b in A,
and the induced edge labels are ![](https://www.scirp.org/html/2-1200055\10b8becf-d708-46d9-9c56-bd070dc212a1.jpg)
P. Jeyanthi and A. Maheswari proved in [10,11] that tadpoles, Cm
Cn, armed crowns, [Pm;
] and,
, the graphs obtained by duplicating an arbitrary vertex and an arbitrary edge of a cycle Cn, total graph of Pn, splitting graph of Pn and fusion of two edges of a cycle Cn are vertex equitable graphs. In this paper, we establish the vertex equitable labeling of a Tp-tree,
where T is a Tp-tree with even number of vertices, the bistar
the caterpillar
and the crown ![](https://www.scirp.org/html/2-1200055\3ad53f95-025b-434d-8088-cd714db2c6d3.jpg)
2. Main Results
Theorem 2.1 Let
and
be any two vertex equitable graphs with equitable labeling f and g respectively. Let u and v be the vertices of G1 and G2 respectively such that
and
Then the graph
obtained from G1 and G2 by identifying the vertices u and v is a vertex equitable graph.
Proof. Clearly
has
edges and
vertices. Let
![](https://www.scirp.org/html/2-1200055\cc723ae2-f960-4976-b2d2-28aea2389195.jpg)
Define ![](https://www.scirp.org/html/2-1200055\cd62a4a5-656e-4c6f-acba-6f892361a25a.jpg)
by
for
and
for
Clearly,
![](https://www.scirp.org/html/2-1200055\dbee1990-1991-47d9-8897-f9eb852169f5.jpg)
Therefore,
and the labels of the edges of the copy of G1 are
and the labels of the edges of the copy of G2 are
Hence,
is a vertex equitable graph.
Theorem 2.2 Let
and
be any two vertex equitable graphs with equitable labeling f and g respectively. Let u and v be the vertices of G1 and G2 respectively such that
and
Then the graph G obtained by joining u and v by an edge is vertex equitable.
Proof. Clearly G has
edges and
vertices. Let
![](https://www.scirp.org/html/2-1200055\4cb931b6-7f03-40b0-b5c9-d780159943e8.jpg)
Define ![](https://www.scirp.org/html/2-1200055\191e70a5-0f3f-41d1-95a7-79389fcf51e0.jpg)
by
if
if
The labels of the edges of the copy of G1 are
and the labels of the edges of the copy of G2 are
and
![](https://www.scirp.org/html/2-1200055\ae551b9c-2a03-4f2f-a420-d3388591f507.jpg)
Hence, G is a vertex equitable graph.
Theorem 2.3 Every Tp-tree is a vertex equitable graph.
Proof. Let T be a Tp-tree with n vertices. By the definition of a transformed tree there exists a parallel transformation P of T such that for the path
we have 1)
, 2)
where
is the set of edges deleted from T and
is the set of edges newly added through the sequence
of the epts P used to arrive the path
Clearly,
and
have the same number of edges.
Now denote the vertices of
successively as
starting from one pendant vertex of
right up to the other.
For
define the labeling f as
![](https://www.scirp.org/html/2-1200055\e7ab5d3a-e2fc-4fb5-92be-d965179096da.jpg)
Then f is a vertex equitable labeling of the path ![](https://www.scirp.org/html/2-1200055\31219e95-5457-497d-b342-18e85417cc35.jpg)
Let
be any edge of T with
and
be the ept that deletes this edge and add the edge
where t is the distance of
from
and also the distance of
from
Let P be a parallel transformation of T that contains
as one of the constituent epts.
Since
is an edge of the path
it follows that
which implies
Therefore
and
are of opposite parity.
The induced label of the edge
is given by
![](https://www.scirp.org/html/2-1200055\33172f64-6e54-4e60-8280-a6ee4cb7fda1.jpg)
Now
![](https://www.scirp.org/html/2-1200055\53a9335d-4e1e-48bd-9682-be1563382b0f.jpg)
Therefore, we have
and hence f is a vertex equitable labeling of the Tp-tree T.
An example for the vertex equitable labeling of a Tp- tree with 12 vertices is given in Figure 2.
Theorem 2.4 Let T be a Tp-tee with even number of vertices. Then the graph
is a vertex equitable graph for all ![](https://www.scirp.org/html/2-1200055\cb0a16d7-cd16-4302-b9f8-422952dcc26d.jpg)
Proof. Let T be a Tp-tree of even order m and the vertex set
Let
be the pendant vertices joined with
by an edge. Then
![](https://www.scirp.org/html/2-1200055\3ca95470-3e2d-4ba0-876f-5f47f664cfc8.jpg)
By the definition of a Tp-tree, there exists a parallel transformation P of T such that for the path
we have 1)
, 2)
where
is the set of edges deleted from T and
is the set of edges newly added through the sequence
of the epts P used to arrive the path
Clearly,
and
have the same number of edges.
Now denote the vertices of
successively as
starting from one pendant vertex of
right up to the other. The labeling f defined by
Figure 2. Vertex equitable labeling of a Tp-tree with 12 vertices.
![](https://www.scirp.org/html/2-1200055\de93e53b-8eda-444c-a37d-0145cfbeb5b4.jpg)
is a vertex equitable labeling graph.
Let
be any edge of T with
let
be the ept that deletes this edge and adds the edge
where t is the distance of
from
and also the distance of
from
Let P be a parallel transformation of T that contains
as one of the constituent epts.
Since
is an edge in the path
it follows that
which implies
Therefore i and j are of opposite parity.
The induced label of the edge
is given by
![](https://www.scirp.org/html/2-1200055\dbd4e218-a786-4c7c-8719-9349b4c5ac8b.jpg)
![](https://www.scirp.org/html/2-1200055\118204a0-a2e3-42bc-88d0-bf5fd7a629dc.jpg)
Therefore, we have
and thus f is a vertex equitable labeling of ![](https://www.scirp.org/html/2-1200055\0e608ea5-676e-4cc6-8b49-33d8d9f3a36f.jpg)
An example for the vertex equitable labeling of
where T is a Tp-tree with 12 vertices is shown in Figure 3.
Let
be a graph obtained from
by attaching n pendant edges at one vertex and
pendant edges at the other vertex.
Theorem 2.5 The bistar
is a vertex equitable graph.
Proof. Let
and
and
be the vertices adjacent to u and v respectively. Now,
has
edges and
vertices. Define
![](https://www.scirp.org/html/2-1200055\6e75c4b2-cd12-4289-b420-db3f871eee97.jpg)
by
if
and
if
Then f is a vertex equitable labeling of ![](https://www.scirp.org/html/2-1200055\a7bc1d35-f2e2-4c60-ba8a-7324163d17d5.jpg)
Theorem 2.6 Let
and
![](https://www.scirp.org/html/2-1200055\b9513707-e69d-4417-82d3-720ed047e6cb.jpg)
Then
is a vertex equitable graph.
Proof. By Theorem 2.5,
is a vertex equitable graph. Let
be the corresponding vertex equitable labeling of
Let
Since
Consider the graphs
and
The number of edges of the graph
is
.
Now, ![](https://www.scirp.org/html/2-1200055\18744530-7b87-4dc6-a8cd-aae4e31834f5.jpg)
Therefore, by Theorem 2.1,
is a vertex equitable graph. Let
be the corresponding vertex equitable labeling of
Again the number of edges of
is even.
Now take
Hence
Also
![](https://www.scirp.org/html/2-1200055\ce8aef45-7050-4ebb-87f5-2b86dc0fc123.jpg)
Therefore, by Theorem 2.1,
is a vertex equitable graph and the number of edges is even. Proceeding like this, at the
step we get
is a vertex equitable graph where
![](https://www.scirp.org/html/2-1200055\374a5f8d-f9a7-450e-b241-680b46296a72.jpg)
Let
be the corresponding vertex equitable labeling of
Take
![](https://www.scirp.org/html/2-1200055\253b367d-b2fa-4362-903a-89f5369e7946.jpg)
Clearly
Now,
Therefore,
is a vertex equitable graph.
An example for the vertex equitable labeling of
if n is odd is given in Figure 4.
An example for the vertex equitable labeling of
if n is even is given in Figure 5.
![](https://www.scirp.org/html/2-1200055\29b058ec-8653-4f49-b6c3-6ef80a9092d0.jpg)
Figure 4. Vertex equitable labeling of S (4, 6, 9, 7 + 1).
![](https://www.scirp.org/html/2-1200055\e36395fa-14f9-44bd-a626-17ea28df4bb9.jpg)
Figure 5. Vertex equitable labeling of S (5, 7, 9, 10, 2 + 1).
Theorem 2.7 The crown
is a vertex equitable graph.
Proof: Let
be the vertices of the cycle Cn and let vi be the vertex adjacent to ui for
Then the vertex set
and the edge set
. Define
for the following cases:
Case 1. ![](https://www.scirp.org/html/2-1200055\58577a11-029a-45de-b3c2-488907ba5128.jpg)
![](https://www.scirp.org/html/2-1200055\31082097-ba0e-4c38-acef-eb089cc0365d.jpg)
![](https://www.scirp.org/html/2-1200055\2c67a472-5ce7-415c-a27f-38c0b892633e.jpg)
Case 2. ![](https://www.scirp.org/html/2-1200055\da56344c-0885-4f2c-96f9-a1a4a22940a1.jpg)
![](https://www.scirp.org/html/2-1200055\87b8d9c0-4b7a-4ee5-a2f2-12aef54f1eea.jpg)
![](https://www.scirp.org/html/2-1200055\184b8309-6af6-4443-a466-d3c2f2122d89.jpg)
Case 3. ![](https://www.scirp.org/html/2-1200055\36c99d4e-a74e-4908-bea0-bebaf964ae05.jpg)
![](https://www.scirp.org/html/2-1200055\e5072c4e-a5e6-416a-bf3d-231c7c501a88.jpg)
![](https://www.scirp.org/html/2-1200055\33a1b929-a40f-435c-a0d0-7c7d5062f3ed.jpg)
![](https://www.scirp.org/html/2-1200055\284a6a8f-6cf9-45ff-b092-d68652fbd002.jpg)
Case 4. ![](https://www.scirp.org/html/2-1200055\f2d603c7-cc69-4d4e-b2d0-35c17b4b56d8.jpg)
![](https://www.scirp.org/html/2-1200055\a3c34119-271f-421d-92d5-21176d4ad5a9.jpg)
![](https://www.scirp.org/html/2-1200055\154e6a91-4130-4b1c-8731-16fa88a99c7a.jpg)
In all the above cases, f is a vertex equitable labeling. Hence
is a vertex equitable graph.
An example for the vertex equitable labeling of
is shown in Figure 6.
Theorem 2.8 The graph
is a vertex equitable graph.
Proof. Let
be the path
Clearly,
has n vertices and
edges. Define
![](https://www.scirp.org/html/2-1200055\169f2fed-c9b4-492e-b5d7-7941abac99f4.jpg)
by
Evidently,
is a vertex equitable graph.