 X
Decomposition of Certain Complete Graphs and Complete Multipartite Graphs into Almost-bipartite Graphs and Bipartite Graphs
G. Sethuraman,
Published in Georgia Southern University
2020
Volume: 7

Issue: 2
Abstract
In his classical paper , Rosa 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 m edges then the complete graph K2m+1 can be decomposed into 2m + 1 copies of T. Inspired by the result of Rosa  many researchers significantly contributed to the theory of graph decompositions using graph labelings. In this direction, in 2004, Blinco et al.  introduced γ-labeling as a stronger version of ρ-labeling. A function g defined on the vertex set of a graph G with n edges is called a γ-labeling if (i) g is a ρ-labeling of G, (ii) G is a tripartite graph 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) g(a) < g(v) for every edge {a, v} ∈ E(G) where a ∈ A, (iv) g(c) − g(¯b) = n. Further, Blinco et al.  proved a significant result that the complete graph K2cn+1 can be cyclically decomposed into c(2cn + 1) copies of any γ-labeled graph with n edges, where c is any positive integer. Recently, in 2013, Anita Pasotti  introduced a generalisation of graceful labeling called d-divisible graceful labeling as a tool to obtain cyclic G-decompositions in complete multipartite graphs. Let G be a graph of size e = d . m. A d-divisible graceful labeling of the graph G is an injective function g : V (G) → {0, 1, 2, . . ., d(m + 1) − 1} such that {|g(u) − g(v)|/{u, v} ∈ E(G)} = {1, 2, . . ., d(m + 1) − 1}\{m + 1, 2(m + 1), . . . , (d − 1)(m + 1)}. A d-divisible graceful labeling of a bipartite graph G is called as a d-divisible α-labeling of G if the maximum value of one of the two bipartite sets is less than the minimum value of the other one. Further, Anita Pasotti  proved a significant result that the complete multipartite graph K(de+1)×2dc can be cyclically decomposed into copies of d-divisible α-labeled graph G, where e is the size of the graph G and c is any positive integer (K(de+1)×2dc contains de + 1 parts each of size 2dc). Motivated by the results of Blinco et al.  and Anita Pasotti , in this paper we prove the following results. i) For t ≥ 2, disjoint union of t copies of the complete bipartite graph Km,n, where m ≥ 3, n ≥ 4 plus an edge admits γ-labeling. ii) For t ≥ 2, t-levels shadow graph of the path Pdn+1 admits d-divisible α-labeling for any admissible d and n ≥ 1. Further, we discuss related open problems. © 2020 Georgia Southern University. All rights reserved.
• 