-labeling of supersubdivided connected graph plus an edge

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.

Keywords

• gamma labeling
• almost-bipartite graph
• cyclic decomposition
• supersubdivision