Physical Sciences and Mathematics Commons^™

Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree

Theory and Applications of Graphs

In his classical paper [14], 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 [14] many researchers significantly contributed to the theory of graph decomposition using graph labeling. 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 …