Geodesic
$L(2,1)$-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 489-518

Voir la notice de l'article provenant de la source Library of Science

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 λ(M^t(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 2^t-1(n+2)-2≤λ(M^t(G))≤ 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 graph and the iterated Mycielski graph of some graph classes.
Keywords: frequency assignment, $L(2,1)$-labeling, Mycielski construction, matching 
@article{DMGT_2024_44_2_a4,
     author = {Dliou, Kamal and El Boujaoui, Hicham and Kchikech, Mustapha},
     title = {$L(2,1)$-labeling of the iterated {Mycielski} graphs of graphs and some problems related to matching problems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {489--518},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a4/}
}
TY  - JOUR
AU  - Dliou, Kamal
AU  - El Boujaoui, Hicham
AU  - Kchikech, Mustapha
TI  - $L(2,1)$-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 489
EP  - 518
VL  - 44
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a4/
LA  - en
ID  - DMGT_2024_44_2_a4
ER  - 
%0 Journal Article
%A Dliou, Kamal
%A El Boujaoui, Hicham
%A Kchikech, Mustapha
%T $L(2,1)$-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 489-518
%V 44
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a4/
%G en
%F DMGT_2024_44_2_a4
Dliou, Kamal; El Boujaoui, Hicham; Kchikech, Mustapha. $L(2,1)$-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 489-518. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a4/