-labeling of supersubdivided connected graph plus an edge. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Sethuraman, G.; Sujasree, M.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 1(2020)
• Page Start: 174
• Page End: 183
• Publication Date: 2020-01-02
• Subjects: Gamma labeling -- Almost-bipartite graph -- Cyclic decomposition -- Supersubdivision
• DOI: 10.1016/j.akcej.2018.11.003
• Languages: English
• ISSNs: 0972-8600

Abstract

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 T is any tree with q edges then the complete graph K 2 q + 1 can be decomposed into 2 q + 1 copies of T . 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 h defined on the vertex set of a graph G with q edges is called a γ -labeling if (i) h is a ρ -labeling of G, (ii) G is tripartite with vertex tripartition ( A, B, C ) with C = { c } and b ̄ ∈ B such that ( b ̄, c ) is the unique edge joining an element of B to c, (iii) for every edge ( a, v ) ∈ E ( G ) with a ∈ A, h ( a ) < h ( v ), (iv) h ( c ) − h ( b ̄ ) = q . Further, Blinco et al. proved a significant result that if a graph G with q edges admits a γ -labeling, then the complete graph K 2 c q + 1 can be cyclically decomposed into 2 c q + 1 copies of the graph G, where c 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 G with q edges, denoted S S D ( G ) if S S D ( G ) is obtained from G by replacing every edge e i of G by a complete bipartite graph K 2, m i, 1 ≤ i ≤ q, (where m i may vary for each edge e i ) in such a way that the ends of e i are identified with the 2 vertices of the vertex part having two vertices of the complete bipartite graph of K 2, m i after removing the edge e i of G . In the graph S S D ( G ), the vertices which originally belong to the graph G are called the base vertices of S S D ( G ) and all the other vertices of S S D ( G ) are called the non-base vertices of S S D ( G ) . More precisely, we prove that if G is a connected graph containing a cycle C k, where k ≥ 6 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 G, S S D ( G ) plus an edge e ˆ admits γ -labeling, where e ˆ is added between a suitably chosen pair of non-base vertices of the graph S S D ( G ) . Also, we discuss a related open problem.