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 [14], Rosa introduced a hierarchical series of labelings called ρ, σ, β and α labeling as a tool to settle Ringel’s Conjecture [13] 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 [14] many researchers significantly contributed to the theory of graph decompositions using graph labelings. In this direction, in 2004, Blinco et al. [6] 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. [6] 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 [4] 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 [4] 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. [6] and Anita Pasotti [4], 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.
About the journal
Journal Theory and Applications of Graphs Georgia Southern University 24709859