GRACEFUL LABELING OF SOME JOIN GRAPHS

Abstract

Let G := (V,E) be a graph with a non-empty vertex set V and edge set E. We call G a (p,q) − graph if |V (G)| = p and |E(G)| = q. A graceful labeling of G is an injection f : V(G) → {0,1,2,...,q} such that the induced mapping f^∗, defined by f^∗(uv) = |f(u)−f(v)| for each edge uv in G, is a bijection from E(G) onto {1,2,3,...,q}. G which admits a graceful labeling is called graceful graph. Let G and H be two disjoint graphs. The join of G and H, denoted by G+H, is the graph obtained from the union of G and H by joining each vertex in G to each vertex in H. If G and H are (m,s) − graph and (n,t) − graph respectively, then the join of both graphs will have size mn+s+t. In this paper, we will present two families of join graphs which have graceful labelings: P(m,s) + I(n,t) and P(m,s) + P(n,t).