Skolem-gracefulness Of K-stars

The graceful labeling is one of the most important branches of Graph Theory, and the concept of Skolem-graceful labeling is a variation of the well-known graceful labeling. One can trace its source from the paper written by Lee in 1991. In this paper, Lee gives the specific definition of Skolem-graceful graph.Let G = (V(G),E(G)) be a simple graph with |V(G)| vertices and |E(G)| edges. Let |V(G)| = p, |E(G)| = q, if there exists f: V(G) â†' {1,2,...,p} be an injective mapping, and define an inducedfunction f':E(G)â†'{1,2,...,q} by setting f'(u,v) = |f(u)-f(v)| for all (u,v)∈E(G). If f' maps E(G) onto {1,2,...,q}, then f is said to be a Skolem-graceful labeling of G, the graph G is said to be a Skolem-graceful graph.We study the Skolem-gracefulness of stars in this paper. Let St(n₁,n₂,...,n_k) denote a k-star with k components K_1,n1 ,K_1,n2,...,K_1,nk, where K_1,nj denotes a star with n_j+1 vertices(1 ≤j≤k).Kishore shows a necessary condition for a k-star to be Skolem-graceful: at least one star has even size or k ≡ 0,1 (mod 4). Obviously, all 1-stars are Skolem graceful. Lee and Wui have proved that 2-stars and 3-stars are Skolem-graceful if and only if at least one star has even size. Denham has proved that all 4-stars are Skolem-graceful. Choudum and Kishore have proved that all 5-stars are Skolem-graceful.The paper gives an algorithm to search the Skolem-graceful labelings of k-stars by computer. Using the symmetric of k-stars, this paper gives an effective bound strategy by dividing vertices into different groups reasonably. We research Skolem-graceful labeling of k-stars by computer when at least one star has even size or k ≡ 0,1 (mod 4). Then we show a sufficient condition for a k-star to be Skolem-graceful: at least one star has even size or k ≡ 0,1 (mod 4). So the study of Skolem-gracefulness of k-stars is end.