Let be a graph with vertices and edges. A graph of size is said to be odd graceful if there exists an injection such that assigning each edge the label or weight results in the set of edge labels being . This concept was introduced in 1991 by Gananajothi. In this paper, we examine the odd graceful labeling of the -tree, denoted as .
Keywords: Graph, Odd graceful labeling, -tree
1. Introduction
The graph considered in this study is finite, connected, and simple.
The symbols and denote the vertex set and edge set
of the graph , respectively.
Additionally, and represent the number of vertices and
edges in , respectively.
Definition 1. [1] Rosa defined a -valuation of a graph with edges as an injection from the vertices
of to the set . This valuation is such
that when each edge is assigned
the label , the
resulting edge labels are distinct.
Definition 2. A graceful labeling possesses the property that there
exists an integer such that
for each edge , either If satisfies this condition, it is
referred to as an -labeling.
Definition 3. [2] A graph of
size is odd graceful if there
exists an injection from to . When each edge is
assigned the label or weight , the resulting edge labels are .
Many types of labeling exist, such as magic, total, antimagic,
harmonious, graceful, and odd-graceful. This work focuses on formulating
odd-graceful labeling for some new graphs. The study of graceful graphs
and graceful labeling was introduced by Rosa. -valuations are functions that
produce graceful labeling. The term ’graceful labeling’ became widely
used after Golomb’s study of such labeling several years later [3]. Graceful labeling and -labeling are among the most
popular classes of graph labeling [4]. It is known that not every graph is graceful.
The Ringel-Kotzig conjecture [5], which posits that all trees are graceful,
remains a well-known open problem.
The concept of odd graceful labeling was introduced by Gnanajothi
[2]. Gnanajothi proposed the
conjecture that all trees are odd-graceful and provided evidence for
this conjecture in trees of order up to 10. Barrientos extended this
conjecture to trees of order up to 12, proving that certain graphs are
odd graceful, such as:
Subdividing each edge exactly once,
Every forest whose components are caterpillars,
Every tree with a diameter of at most five,
All disjoint unions of caterpillars.
Barrientos also conjectured that every bipartite graph is odd
graceful.
Eldergill generalized Gnanajothi’s results on stars, demonstrating
that a graph obtained by joining one endpoint from each of an odd number
of paths of equal length is odd graceful [6]. Gao worked on the union of graphs and proved
that unions of paths, stars, cycles , , and
unions of cycles of order divisible by 4 are odd or both types of
graceful.
S.K. Vaidya and L.Bijukumar investigated odd graceful labeling,
focusing on combining two copies of with a path and two copies of a cycle sharing a common edge, leading to
various results.
Graph labeling has become an increasingly useful mathematical model
for a wide range of applications, including ambiguities in X-Ray
crystallography, communication network labeling, and circuit layout
optimization. Most graph labeling problems involve three elements:
A set of numbers from
which the labels are chosen,
A rule assigning a value to each edge,
A condition that these values must satisfy.
Motivated by Gananajothi’s research, many other graphs have been
studied since then, which are odd graceful, leading to many new results.
However, there still exist many interesting open problems. Inspired by
the research in [2, 7], we
began investigating the odd graceful labeling of the -tree and its disjoint union with other
graph families.
In this work, we demonstrate that a subclass, namely the -tree , admits odd graceful labeling. We
also prove that the graph obtained by the disjoint union of a -tree with a path , a star , a bistar , and a ladder are odd graceful graphs.
Firstly, we define some terms that will aid in understanding the
subsequent work.
Definition 4. [4] A path is a tree with vertex set and
edge set .
Definition 5. [4] Let
define the central vertex of star , and let , be its leaves.
Definition 6. A bistar is a graph obtain by
joining the central vertices of two star graphs.
Definition 8. Let G be a graph with the set of
vertices and edges as we call it -graph and it shall be denoted by
W(n).
Definition 9. Suppose that we have k isomorphic
copies of w-graphs W(n). A w-tree WT(n,k) is a tree obtain by taking a
new vertex a and joining it with , where .
2. Odd-gracful labeling of
w-tree
In this section, we will define the odd graceful labeling of
W-tree.
Theorem 1. For , admits
odd graceful labeling if .
Proof. Let G be a graph , we denote the vertex and edge set
of G as follows:
and where and .
Now, we define the labeling as follows where For and
3. Disjoint
union of two isomorphic copies of w-tree
The odd graceful labeling of disjoint union of two isomorphic copies
of w-tree will presented in this section.
Theorem 2. Let be an odd graceful graph
for .
Proof. Let be a
graph, we denote the vertex and edge set of as follows:
then and Now we define the
labeling as follows. where
For and
Now for the apex vertex and , we have:
4. Disjoint
union of -tree with other families of
Graphs
The odd graceful labeling of w-tree with some other known families of
graphs like path, star, bistar, lader has been formulated in this
section.
4.1. Disjoint union of
-tree with path
Theorem 3. A graph admits the odd
graceful labeling if .
Proof. Let be a
graph, where represents the total
number of edges of path and
and represents the total number of
edges of path and represents the total number of vertices
of path . The vertex and the
edge set of can be represented as
follows: and
then and Now we define the
labeling as follows. We have different
schemes for both path and w-tree,
where Now for the w-tree, we have the following scheme
where For and
4.2. Disjoint union of
-tree with star
Theorem 4. Let admits the
odd graceful labeling if .
Proof. Let ba a graph
and is the total number of edges
of star and w-tree and represents the total number of
edges of star and represents the total number of
vertices. The vertex and edge set of graph is follows:
and
then and
Now we define
the labeling as follows. Now we have different
schemes for both star and w-tree.
For star , we have the
following scheme:
where , Now for the w-tree, we have the following scheme
where For and
4.3. Disjoint union
of -tree with bistar
Theorem 5. Let admits odd
graceful labeling if .
Proof. Let ba a graph
and is the total number of edges
of bistar and w-tree
and represents the total number of
edges of bistar and represents the total number of
vertices. The vertex and edge set of graph is follows:
and
then and
Now we define the labeling as follows. Now we have different schemes for both
bistar and w-tree. As we know that a bistar consist of two isomorphic
copies of a star, so we discuss each star separately.
Now for the first star. we have the following scheme:
where , Now for the second star. we have the following
scheme:
where ,
Now for the w-tree, we have the following scheme where For and
4.4. Disjoint union of
w-tree with lader
Theorem 6. Let admits odd
graceful labeling if .
Proof. Let ba a graph
and is the total number of edges
of ladder and w-tree and represents the total number of
edges of ladder and represents the total number of vertices
of path . The vertex and edge
set of graph is follows:
and
then and Now we define the
labeling as follows.
Now we have different schemes for both lader and w-tree.
where ,
Now for w-tree we have following scheme, where
is the least edge weight in the
ladder graph.
where For and
5. Conclusion
In this paper, we have demonstrated that a specific subclass, the
W-tree denoted by , admits
an odd graceful labeling. Additionally, we prove that graphs obtained
through the union of a W-tree with various other graphs-namely,
a path , a star , a bistar , and a ladder -are also odd
graceful graphs. However, a more comprehensive understanding of the odd
graceful labeling of W-trees requires further investigation.
Conflict of
Interest
The authors declare no conflict of interest.
References:
Rosa, A., 1966, July. On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome (pp. 349-355).[Google Scholor]
Gnanajothi, R.B., 1991. Topics in graph theory (Doctoral dissertation, Ph. D. Thesis, Madurai Kamaraj University).[Google Scholor]
Golomb, S.W., 1972. How to number a graph, Graph Theory and Computing. Academic Press, New York, 23, p.37.[Google Scholor]
Baca, M. and Miller, M., 2008. Super edge-antimagic graphs: A wealth of problems and some solutions. Universal-Publishers.[Google Scholor]
Wang, T.M., Yang, C.C., Hsu, L.H. and Cheng, E., 2015. Infinitely many equivalent versions of the graceful tree conjecture. Applicable Analysis and Discrete Mathematics, pp.1-12.[Google Scholor]
Daoud, S.N., 2017. Edge odd graceful labeling of some path and cycle related graphs. AKCE international journal of graphs and combinatorics, 14(2), pp.178-203.[Google Scholor]
Gallian, J.A., 2018. A dynamic survey of graph labeling. Electronic Journal of combinatorics, 1(DynamicSurveys), p.DS6.[Google Scholor]
