Study On Some Problems In Graceful Graph

A graceful graph has great applied value in the x- radial crystalloid study, radar and communication net, coding, radio astronomy. Thus, graceful graph is one of active subject in graph theory. In addition, the methods to solve graceful graph need some especial skills and flexible ways. These methods can supply to some relative branches in graph theory as some constructive and valuable ways. While as for the bases of a kind of some practical problems, studying of graceful graphs has practical applied value and basal studying value. This thesis is just on studying some problems of graceful graphs.Rose^[2] got the sufficient and necessary condition t hat C_n, a kind of special Euler Graph, is the graceful graph. After Feng^[2] got that the graph the sufficient and necessary condition that ω_m,n is the graceful graph. In Chapter 3 we definedthe graph ω_{m1,m2,…,mn} , and proved that ω_{m1,m2,…,mn} is the graceful graph and alternating graph when m₁,m₂,…,m_n≡0(mod4). After that we defined the string graph ω_{m1,m2,…,mn,mn+1}, and proved that the string graph ω_{m1,m2,…,mn,mn+1} is the graceful graph with m₁,m₂,…,m_n≡0(mod 4) m_n+1 ≡ 3(mod 4).In 1994, Du Z.T. and Sun H.Q.^[9] proved the gracefulness of the digraph n·C_2p with (n≡ 0(mod 2)). Based on the result, they conjectured that the digraph n·C_2p+1 (n≡0(mod 2)) is a graceful digraph. Since then, it is proved that the conjecture is true for p=1,2,3 by different authors[9-14]. In Chapter 4, we prove that the conjecture is true for p = 4, and three different graceful labelings of the digraphn·C₉ (n≡0(mod 2)) are given.In Chapter 5, firstly, we discussed the gracefulness of union of arbitrary n complete bipartite graphs. Secondly, a kind of unconnected graph, the graphUK_mi+1.2 is defined. Furthermore we proved that the unconnected graphs ofUK_mi+1.2 is a graceful graph, and it is also an alternating graph. Thirdly, we provedthat the graph is the graceful graph and an alternating graph when mj belongs to the set { 6k_i, 6k_i+1,6k_i + 2,6k_i + 3,6k_i + 4,6k_i+ 5 } for i = 1,2,…,n.Actually, we shown two kinds of graceful labelings of when m_i, is in the set { 6k_i,6k_i+1,6k_i+ 2,6k_i + 3,6k_i + 4,6k_i + 5 } for i = 1,2,…,n . And then, we gave another graceful labeling of the graph P_n³, and prove that the labeling is gracefuland alternating. Finally, we pointed out the mistake of the labeling of the graph P_n³( where n = 6k + 4 n = 6k + 5) discussed in [20]. We corrected the mistake and got the corresponding correct labeling. We shown another graceful labelings for thegraph P_n³.