





















In this paper, we study the $L(2, 1)$-Labeling of the Mycielski and the iterated Mycielski of graphs in general. For a graph $G$ and all $t\geq 1$, we give sharp bounds for $λ(M^t(G))$ the $L(2, 1)$-labeling number of the $t$-th iterated Mycielski in terms of the number of iterations $t$, the order $n$, the maximum degree $\bigtriangleup$, 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 of a graph, with some applications to special graphs. For all $t\geq 2$, we prove that for any graph $G$ of order $n$, we have $2^{t-1}(n+2)-2\leq λ(M^t(G))\leq 2^{t}(n+1)-2$. Thereafter, we characterize the graphs achieving the upper bound $2^t(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 $2^{t-1}(n+2)-2$. We determine the $L(2, 1)$-labeling number for the Mycielski and the iterated Mycielski of some graph classes.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。