NEAR FELICITOUS DIFFERENCE LABELING GRAPH
Dr. A. Punitha Tharani
Associate Professor, Department of Mathematics, St. Mary’s College (Autonomous),
Thoothukudi – 628 001,
Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli – 627 012,
Tamil Nadu, India
E.S.R. Francis Vijaya Rani
Research Scholar, Register No: 19122212092004
Department of Mathematics, St. Mary’s College (Autonomous),
Thoothukudi – 628 001.
(Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli, TamilNadu, India)
francisvijayarani@gmail.com
Abstract
A simple graph G is called Near Felicitous if there exists a 1 – 1 function f: V (G)
in such that the set of induced edges labels 
are all distinct when the subtraction is taken modulo q+1 with residues
. In this paper, we prove that Path, Complete Bipartite Graph, Fan, Ladders (n
), Peterson are Near Felicitous Difference Labeling Graph. As a consequence, some families of graphs are shown to be non – near felicitous difference labeling.
Keywords: Near Felicitous Difference Labeling (NFDL), Path, Cycle, Complete Bipartite Graph, Fan, Ladders, Peterson Graph
I.INTRODUCTION
In 1966, Rosa [3] introduced 
- valuation of a graph and subsequently Golomb introduced graceful labeling. In 1980, Graham and Slonae [2] introduced the harmonious labeling of a graph. Several graph labelings have been found in Gallian survey [1]. Lee and schmeichel and shee [4] introduced the concept of felicitous graph as a generalization of harmonious graph. V. Lakshmi Alias Gomathi, A. Nagarajan, A. Nellai Murugan introduced the concept of felicitous labeling of a graph [5].A Felicitous Difference Labeling of a graph G, with q edges is an injection f : V(G)
in such a way that each edge e = uv, is labeled as . The resulting labels of the edges are distinct and form.
Near Felicitous labeling graph was introduced by V. Lakshmi Alias Gomathi, A. Nagarajan, A. Nellai Murugan[6]. It motivates us to define the concept of near felicitous difference labeling graph.
II. Preliminaries
Definition 2.1: A Path 
is a walk in which all the vertices are distinct.
Definition 2.2: A Cycle 
is a Closed Path.
Definition 2.3: A Complete Bipartite graph
is a bipartite graph with bipartition 
such that every vertex of 
is joined to all the vertices of V, Where | | = m and |
| = n.
Definition 2.4: The fan 
(n ≥ 2) is obtained by joining all vertices of (Path of n vertices) to a further vertex called the center and contains n + 1 vertex and 2n-1 edges. i.e. = 
+ 
.
Definition 2.5: The ladder 
(n ≥ 2) is the product graph 
x
which contains 2n vertices and 3n – 2 edges.
Definition 2.6: Peterson graph with 10 vertices and 15 edges. It is most commonly drawn as pentagon with a pentagram inside with five spokes.
III. Main Results
Definition 3.1: A Felicitous Difference Labeling of a graph G, with q edges is an injection f : V(G) in such a way that each edge e = uv, is labeled as . The resulting labels of the edges are distinct and form. A graph that admits a Near Felicitous Difference Labeling (FDL) is called Near Felicitous Difference Labeling Graph.
Example: 3.1.1 NFD labeling of the cycle 
is given in fig. 1
|
9 |
|
1 |
|
7 |
|
3 |
|
2 |
|
0 |
|
5 |
Fig. 1
Theorem 3.2: Any Path 
is a NFDL.
Proof: Let V () = 
and E () =
. Then 
= n and 
= n – 1. Define f:V ()
as follows:
, 
, 
Continuing in this way, we get the induced edge labels 
are all distinct.
Example 3.3: The FD labeling of 
and 
are given in fig. 1 and 2 respectively.
|
6 |
|
1 |
|
4 |
|
0 |
|
2 |
|
3 |
Fig. 2
|
11 |
|
1 |
|
9 |
|
0 |
|
7 |
|
2 |
|
8 |
|
4 |
|
5 |
|
3 |
|
6 |
Fig. 3
Theorem 3.4: For each m, n
1, the complete bipartite graph 
is NFDL graph.
Proof: Let the bipartition of be (X, Y) where 
and
.
Assume that, m 
n. But 
Then, a near felicitous labeling of is
f(
) = mn+1
f(
) = i, i = 1,2,…..m and
f(
) =
, 
Then the induced edge labels are distinct. Hence admits NFDL graph.
Example 3.5: The NFD labeling of 
are given in fig 5 respectively.
|
1 |
|
2 |
|
9 |
|
7 |
|
5 |
|
3 |
Fig. 4
Theorem 3.6: For a fan graph,
is NFDL graph for n 
2.
Proof: Let
be the centre of fan. Define f: V ()
as follows:
f() = 2n
f(
) = 
f(
) = 
let 
be the induced edge labeling of f. Then
Then the induced edge labels are all distinct. Hence from the above labeling pattern, the graph admits NFDL graph.
Example 3.7: The NFD labeling of 
are given in fig 6 respectively.
Fig. 5
Theorem 3.8: All ladders n
2 are NFDL graph.
Proof: Define f: V (
)
is defined as follows:
f(
) = 1
f() = 
f(
) = 2
f() = 
f(
) = 3n – 1
f(
) = 
f(
) = 3n – 3
f(
) = 
Then the induced edges labels are distinct. Hence admits is a NFDL graph.
Example 3.9: The NFD labeling of 
are given in fig 7 respectively.
Fig. 6
Theorem 3.10: The Peterson graph is NFDL graph. The following fig. 7
Fig. 7
Results 3.11: is a NFDL graph if n = 4k, k = 1,2,3,….
Results 3.12: Every Star graph is FDL graph. But Every Star graph is not NDFL Graph.
Results 3.13: Let G be a graph with odd number of edges and f: V (G)
be a near odd edge labeling of G. Then f is not near felicitous labeling of G.
Results 3.14: Let G be a graph with even number of edges and f: V (G) be a near even edge labeling of G. Then f is not near felicitous labeling of G.
Results 3.15: Let G be a graph with even number of edges and f: V (G) be a near odd edge labeling of G. Then f is not near felicitous labeling of G.
III. Conclusion
The Study of labeled graph is important due to its diversified applications. All graphs are not NFDL graphs. It is very interesting to investigate graphs which admit NFD Labeling. In this paper, we proved that Path, Complete Bipartite Graph, Fan, Ladders (n
), Peterson graph are Near Felicitous Difference Labeling Graph. We have already investigated graphs which are NFDL graph only for certain cases and have planned to investigate the NFD labeling of some special cases of path and cycle related graphs in our next paper.
IV. References