非连通图(P_1∨P_n)∪G_r和(P_1∨P_n)∪(P_3∨-■_r)及W_n∪St(m)的优美性

Gracefulness of Unconnected Graphs(P_1∨P_n)∪G_r,(P_1∨P_n)∪(P_3∨■_r) and W_n∪St(m)

讨论非连通图(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨■r)及Wn∪St(m)的优美性,证明了如下结论:设n,m为任意正整数,s=[n/2],r=s-1,Gr是任意具有r条边的优美图,则当n≥4时,非连通图(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨■r)是优美图;当n≥3,m≥s时,非连通图Wn∪St(m)是优美图.其中,Pn是n个顶点的路,Kn是n个顶点的完全图,K-n是Kn的补图,G1∨G2是图G1与G2的联图,Wn是n+1个顶点的轮图,St(m)是m+1个顶点的星形树.

The present paper deals with the gracefulness of three kinds of unconnected graphs （ Pi ∨ P.） L/Gr, （P1∨Pn）∪ （P3∨ Kr） and Wn ∪ St（ m）, and proves the following results： for positive integers n and m, let s = [ n/2 ], r = s - 1, Gr be a graceful graph with r-edges, if n ≥4, then the unconnected graphs （ PI V P.） U Gr and （P1∨ Pn ） ∪ （ P3 ∨ Kr ） are both graceful graphs ; if n ≤ 3 and m ≥s, then the unconnected graph Wn∪St（m） is a graceful graph, where P. is an n-vertex path, K. is an n-vertex complete graph, K. is the complement of graph Kn, graph G1 ∨ G2 is the join graph of GI and G2, Wn is an （ n ＋ 1 ） -vertex wheel graph and St（m） is an （ m ＋ 1 ） -vertex star tree.