A Graceful Graph

Let G=(V,E) be a simple graph with |V| vertices and |E| edges. Let f: V(G) â†'{0, 1, 2, ..., |E|] be an injective mapping. Define an induced functionf ': E(G)â†'{1, 2, ..., |E|] by setting f'(u, v) = |f(u) -f(v) | for all (u, v) ∈ E. If f' maps E onto {1, 2, ..., |E|}, then f is said to be a graceful labeling of G. A graph is graceful if it has a graceful labeling.Given t cycles Cn of length n>3, each with a fixed vertex v0i, i=1, 2, .... t, let Cn(t) denote the graph obtained from the union of the t cycles by identifying the t fixed vertices(v01 = v02= ... =v0t). A necessary condition for an Eulerian graph with m edges to be graceful is that nt=0,3(mod 4), hence a necessary condition for Cn(r) to be graceful is that nt = 0, 3(mod 4). K. M. Koh et al. conjectured that Cn(t) is graceful if and only if nt = Q, 3 (mod 4). The conjecture has been shown true for n=3, 4p, 4p+2(p>1).In this paper, a graceful labeling of CsW is given, and the graceful labeling is proved to be true, hence the above conjecture is shown to be true for n = 5.