L(2,1)-Labeling of the iterated Mycielski of graphs and some related\n to matching problems

2021/02/27 by Kamal Dliou, Dliou, Kamal, Hicham El Boujaoui +3
Computer Science · Engineering · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2103.00341

Abstract

In this paper, we study the L(2, 1)-Labeling of the Mycielski and the\niterated Mycielski of graphs in general. For a graph G and all t\≥ 1, we\ngive sharp bounds for \λ(M^t(G)) the L(2, 1)-labeling number of the\nt-th iterated Mycielski in terms of the number of iterations t, the order\nn, the maximum degree bigtriangleup, and \λ(G) the L(2,\n1)-labeling number of G. For t=1, we present necessary and sufficient\nconditions between the 4-star matching number of the complement graph and\n\λ(M(G)) the L(2, 1)-labeling number of the Mycielski of a graph, with\nsome applications to special graphs. For all t\≥ 2, we prove that for any\ngraph G of order n, we have 2^t-1(n+2)-2\≤ \λ(M^t(G))\≤\n2^t(n+1)-2. Thereafter, we characterize the graphs achieving the upper bound\n2^t(n+1)-2, then by using the Marriage Theorem and Tutte's characterization\nof graphs with a perfect 2-matching, we characterize all graphs without\nisolated vertices achieving the lower bound 2^t-1(n+2)-2. We determine the\nL(2, 1)-labeling number for the Mycielski and the iterated Mycielski of some\ngraph classes.\n

Citations

• On the Complexity of General Graph Factor Problems
• On Representatives of Subsets

Related

• Graph Labeling with Distance Conditions and the Delta Squared Conjecture
• Path covering number and L(2,1)-labeling number of graphs
• A characterization of L(2, 1)-labeling number for trees with maximum degree 3
• A linear time algorithm for L(2,1)-labeling of trees
• A tight upper bound on the (2,1)-total labeling number of outerplanar graphs