The L(2,1)-Labelings On General Mycielski Graphs And Full-Colorable Graphs

The labeling problem of graphs is one of the most basic and important branch in graph theory, and there are extensive applications in true life. For a general graph G, it is an NP-hard problem to determine the exact value ofλ(G) . For some special graph G, we try to research the bounds or the exact value ofλ(G). In this thesis , we will consider the progress of the L(2,1)-labeling problems. The content of the thesis mainly involve the following three parts:(l)we discuss the L(2,1)-labeling number of the General Mycielski graphs.(2)we discuss the structure of the graphs satisfyingλ(G) = (?)(G) .(3)we discuss the extended labeling problem.In the first part, we determine the L(2,1)- labeling number of the General Mycielski graphs of some special graphs, our main results are: (1) Let M_p(P_n) be the general Mycielski graph of P_n .λ(M_p(P_n)) =4 when n = 2, p≥2 ;λ(M_p(P_n)) =5 when n=3,p = 2;λ(M_p(P_n)) =6 when n≥3, p≥3. (2) Let M_p(K_1,n-1)be the general Mycielski graph of K_1,n-1.λ(M_p(K_1,n-1)) = 2n-1 when p = 2;λ(M_p(K_1,n-1)) = 2n when p≥3. (3) Let M_p(K_n) be the general Mycielski graph of K_n .λ(M_p(K_n)) =4 when n=2 ;λ(M_p(K_n)) = 3n-2 when n≥3. (4) Let M_p(C_n) be the general Mycielski graph of C_n.λ(M_p(C_n)) =7 when n =3,4,5.In the second part, we discuss the consecutive labeling problems. In [9], C.Lu et al prove that: (1) Let G be a graph of order n and size m. If m≤n - 2, thenλ(G) = (?)(G) except that G is the disjoint union of several K₂. (2)Let G be a graph of order n. If C(G)≥[(n+1)/2] , thenλ(G) = (?)(G) . These graphs satisfyingλ(G) =(?)(G) are all disconnected. In chapter 3, we prove that some General Mycielski graphs are the connected graphs satisfyingλ(G) = (?)(G).In the third part, we extend the labeling problem from two constraints to three constraints, study the upper bounds of L(3,2,1)-labeling number of Halin graph and the General Mycielski graph of K_n. The main results are: (1) Let G be the Halin graph with maximum degreeâ–³, thenλ_3,2,1(G)≤5â–³+ 16. (2) Let m_p (K_n) be the General Mycielski graph of K_n, thenλ_3,2,1(M_p(K_n))≤7n-4.