Abstract
Rosa, in his classical paper (Rosa, 1967) introduced a hierarchical series of labelings called and
labeling as a tool to settle Ringel’s Conjecture which states that if
is any tree with
edges then the complete graph
can be decomposed into
copies of
. Inspired by the result of Rosa, many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco, El-Zanati and Vanden Eynden introduced
-labeling as a stronger version of
-labeling. A function
defined on the vertex set of a graph
with
edges is called a
-labeling if
(i) is a
-labeling of
,
(ii) is tripartite with vertex tripartition
with
and
such that
is the unique edge joining an element of
to
,
(iii) for every edge with
,
,
(iv) .
Further, Blinco et al. proved a significant result that if a graph with
edges admits a
-labeling, then the complete graph
can be cyclically decomposed into
copies of the graph
, where
is any positive integer. Motivated by the result of Blinco et al., we show that a new family of almost bipartite graphs each admits
-labeling. The new family of almost bipartite graphs is defined based on the supersubdivision graph of certain connected graph. Supersubdivision graph of a graph was introduced by Sethuraman and Selvaraju in Sethuraman and Selvaraju (2001). A graph is said to be a supersubdivision graph of a graph
with
edges, denoted
if
is obtained from
by replacing every edge
of
by a complete bipartite graph
,
, (where
may vary for each edge
) in such a way that the ends of
are identified with the 2 vertices of the vertex part having two vertices of the complete bipartite graph of
after removing the edge
of
. In the graph
, the vertices which originally belong to the graph
are called the base vertices of
and all the other vertices of
are called the non-base vertices of
. More precisely, we prove that if
is a connected graph containing a cycle
, where
and having a vertex of degree two with one of its adjacent vertices of degree one and its other adjacent vertex is of degree at least two, then certain supersubdivision graph of the graph
,
plus an edge
admits
-labeling, where
is added between a suitably chosen pair of non-base vertices of the graph
. Also, we discuss a related open problem.