L(2, 1)-LABELING OF THE ITERATED MYCIELSKI GRAPHS OF GRAPHS AND SOME PROBLEMS RELATED TO MATCHING PROBLEMS.

In this paper, we study the L(2, 1)-labeling of the Mycielski graph and the iterated Mycielski graph of graphs in general. For a graph G and all t ≥ 1, we give sharp bounds for λ(Mt(G)) the L(2, 1)-labeling number of the t-th iterated Mycielski graph in terms of the number of iterations t, the order n of G, the maximum degree △, and λ(G) the L(2, 1)-labeling number of G. For t = 1, we present necessary and sufficient conditions between the 4-star matching number of the complement graph and λ(M(G)) the L(2, 1)-labeling number of the Mycielski graph of a graph, with some applications to special graphs. For all t ≥ 2, we prove that for any graph G of order n, we have 2t-1(n + 2) - 2 ≤ λ(Mt(G)) ≤ 2t(n + 1) - 2. Thereafter, we characterize the graphs achieving the upper bound 2t(n+1)-2, then by using the Marriage Theorem and Tutte's characterization of graphs with a perfect 2-matching, we characterize all graphs without isolated vertices achieving the lower bound 2t-1(n+2)-2. We determine the L(2, 1)-labeling number for the Mycielski graph and the iterated Mycielski graph of some graph classes. [ABSTRACT FROM AUTHOR]