A Class Of Graceful Graphs

The graceful labeling is one of the important branches of Graph Theory. One can trace its source from a conjecture given by G. Ringel in 1963 and a paper written by A. Rosa in 1966. In 1972, S. W. Golomb gives the definition about graceful graph.Let G=(V(G)JS(G)) be a simple graph with |V(G)| vertices and |E(G)| edges. Let |E(G)|=q, if there exists f.V(G)â†'{0,1,2,...,q} be an injective mapping, and define an induced function f:E(G)â†'{1,2,.. .,q} by settingf(w,v)=|f(u) -f(v)l for all (u,v)∈E(G). If f' maps E(G) onto {1,2,.. .,q), then f is said to be a graceful labeling of G, the graph G is said to be a graceful graph.Let Cn denote the cycle with n vertices, and C_n^t denote the graphs consisting of/ copies ofCn with a vertex in common. This paper do some research on the graceful labelings of C_m^t for nis odd. Let v₀ⁱ ,v₁ⁱ,v₂ⁱ……v_n-1ⁱ., be the vertices of i-th{1≤i≤t) cycle Cn of length n, v₀ⁱ=v for all i. A necessary condition for an Euler graph with q edges to be graceful is that q≡0,3(mod 4). Since the graph C_n^t ) is Euler graph, if C_n^t is graceful then nt≡0,3(mod 4).In 1979, K. M. Koh et al. conjectured that C_n^t is graceful if and only if nt≡o,3(mod 4). The conjecture has been shown true for n=3,5,4p,4p+2(p≥l).The paper gives an algorithm to search the graceful labelings of graph C_n^t by computer. Using the symmetric of graph C_n^t, this paper gives an effective bound strategy by dividingvertices into different groups reasonably. We research graceful labelings of C_n^t by computer and prove that Koh's conjecture is true for n=7,9,11,13.