Graceful Labeling of some Join Graphs and the Subdivision of Complete Bipartite Graphs

The join of graphs G and H , denoted by G + H , is the graph obtained from the disjoint union of G and H by joining each vertex in G to each vertex in H . An edge u w is said to be subdivided if u w is replaced by the path P : u v w , where v is the new vertex. A graph obtained by subdividing each edge of a graph G is called the subdivision of G , and is denoted by S ( G ). In this paper, we present results on the gracefulness of some join graphs, namely, T + P n , T + P n ( m ), C 4 + O p , P s ( m ) + P t ( n ) for some m , n , s , t and T is a graceful tree. We also show that the subdivision graph S ( K m , n ) of complete bipartite graph K m , n is graceful.