DECOMPOSITION OF COMPLETE GRAPHS AND COMPLETE BIPARTITE GRAPHS INTO COPIES OF P3n OR S2(Pn 3) AND HARMONIOUS LABELING OF K2 + Pn
Abstract: In this paper, the
graphs Pn 3 and S2(Pn 3) are shown to admit an α-valuation, where Pn 3 is the
graph obtained from the path Pn by joining all the pairsof vertices u; v of Pn
with d(u; v) = 3 and S2(Pn 3) is the graph obtained from Pn 3 bymerging the
centre of the star Sn1 and that of the star Sn2 respectively at the two unique
2-degree vertex of Pn3 (the origin and terminus of the path Pn contained in P 3
n). It follows from the significant theorems due to Rosa [1967] and EI-Zanati
andVanden Eynden [1996] that the complete graphs K2cq+1 or the complete
bipartitegraphs Kmq;nq can be cyclically decomposed into the copies of Pn 3 or
copies ofS2(Pn 3), where c; m; n are arbitrary positive integer and q denotes
either jE(Pn 3)j or jE(S2(Pn 3))j. Further, it is shown that join of complete
graph K2 and path Pn, denoted K2 + Pn, for n ≥ 1 is harmonious graph.
Author: P. Selvaraju and G.
Sethuraman
Journal Code: jpmatematikagg110008
