X
-labeling of supersubdivided connected graph plus an edge
G. Sethuraman,
Published in Taylor and Francis Ltd.
2020
Volume: 17

Issue: 1
Pages: 174 - 183
Abstract
Rosa, in his classical paper (Rosa, 1967) introduced a hierarchical series of labelings called (Formula presented.) and (Formula presented.) labeling as a tool to settle Ringel’s Conjecture which states that if (Formula presented.) is any tree with (Formula presented.) edges then the complete graph (Formula presented.) can be decomposed into (Formula presented.) copies of (Formula presented.). 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 (Formula presented.) -labeling as a stronger version of (Formula presented.) -labeling. A function (Formula presented.) defined on the vertex set of a graph (Formula presented.) with (Formula presented.) edges is called a (Formula presented.) -labeling if (i) (Formula presented.) is a (Formula presented.) -labeling of (Formula presented.), (ii) (Formula presented.) is tripartite with vertex tripartition (Formula presented.) with (Formula presented.) and (Formula presented.) such that (Formula presented.) is the unique edge joining an element of (Formula presented.) to (Formula presented.), (iii) for every edge (Formula presented.) with (Formula presented.), (Formula presented.), (iv) (Formula presented.). Further, Blinco et al. proved a significant result that if a graph (Formula presented.) with (Formula presented.) edges admits a (Formula presented.) -labeling, then the complete graph (Formula presented.) can be cyclically decomposed into (Formula presented.) copies of the graph (Formula presented.), where (Formula presented.) is any positive integer. Motivated by the result of Blinco et al., we show that a new family of almost bipartite graphs each admits (Formula presented.) -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 (Formula presented.) with (Formula presented.) edges, denoted (Formula presented.) if (Formula presented.) is obtained from (Formula presented.) by replacing every edge (Formula presented.) of (Formula presented.) by a complete bipartite graph (Formula presented.), (Formula presented.), (where (Formula presented.) may vary for each edge (Formula presented.)) in such a way that the ends of (Formula presented.) are identified with the 2 vertices of the vertex part having two vertices of the complete bipartite graph of (Formula presented.) after removing the edge (Formula presented.) of (Formula presented.). In the graph (Formula presented.), the vertices which originally belong to the graph (Formula presented.) are called the base vertices of (Formula presented.) and all the other vertices of (Formula presented.) are called the non-base vertices of (Formula presented.). More precisely, we prove that if (Formula presented.) is a connected graph containing a cycle (Formula presented.), where (Formula presented.) 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 (Formula presented.), (Formula presented.) plus an edge (Formula presented.) admits (Formula presented.) -labeling, where (Formula presented.) is added between a suitably chosen pair of non-base vertices of the graph (Formula presented.). Also, we discuss a related open problem. © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.