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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {2},
     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
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
%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/

[1] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6. https://doi.org/10.1016/0012-365X(82)90048-6

[2] M. Borowiecki, P. Borowiecki, E. Drgas-Burchardt and E. Sidorowicz, Graph classes generated by Mycielskians, Discuss. Math. Graph Theory 40 (2020) 1163–1173. https://doi.org/10.7151/dmgt.2345

[3] T. Calamoneri, The L(h, k)-labelling problem: An updated survey and annotated bibliography, Comput. J. 54 (2011) 1344–1371. https://doi.org/10.1093/comjnl/bxr037

[4] M. Caramia and P. Dell'Olmo, A lower bound on the chromatic number of Mycielski graphs, Discrete Math. 235 (2001) 79–86. https://doi.org/10.1016/S0012-365X(00)00261-2

[5] G.J. Chang, L. Huang and X. Zhu, Circular chromatic numbers of Mycielski's graphs, Discrete Math. 205 (1999) 23–37. https://doi.org/10.1016/S0012-365X(99)00033-3

[6] G.J. Chang and D. Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309–316. https://doi.org/10.1137/S0895480193245339

[7] J. Fiala, T. Kloks and J. Kratochvíl, Fixed-parameter complexity of \lambda-labelings, Discrete Appl. Math. 113 (2001) 59–72. https://doi.org/10.1016/S0166-218X(00)00387-5

[8] D.C. Fisher, P.A. McKenna and E.D. Boyer, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs, Discrete Appl. Math. 84 (1998) 93–105. https://doi.org/10.1016/S0166-218X(97)00126-1

[9] J.P. Georges, D.W. Mauro and M.A. Whittlesey, Relating path coverings to vertex labellings with a condition at distance two, Discrete Math. 135 (1994) 103–111. https://doi.org/10.1016/0012-365X(93)E0098-O

[10] D. Gonçalves, On the L(p,1)-labelling of graphs, Discrete Math. 308 (2008) 1405–1414. https://doi.org/10.1016/j.disc.2007.07.075

[11] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595. https://doi.org/10.1137/0405048

[12] W.K. Hale, Frequency assignment: Theory and applications, {Proc. IEEE } 68 (1980) 1497–1514. https://doi.org/10.1109/PROC.1980.11899

[13] F. Havet, B. Reed and J.-S. Sereni, L(2,1)-labelling of graphs, in: Proc. 19th Annual ACM-SIAM Symp. Discrete Algorithms SODA08, (San Francisco, California, USA 2008) 621–630.

[14] A.J. Hoffman and R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM Journal of Research and Development 4 (1960) 497–504. https://doi.org/10.1147/rd.45.0497

[15] D.G. Kirkpatrick and P. Hell, On the complexity of general graph factor problems, SIAM J. Comput. 12 (1983) 601–609. https://doi.org/10.1137/0212040

[16] M. Larsen, J. Propp and D. Ullman, The fractional chromatic number of Mycielski's graphs, J. Graph Theory 19 (1995) 411–416. https://doi.org/10.1002/jgt.3190190313

[17] W. Lin and P.C.B. Lam, Star matching and distance two labelling, Taiwanese J. Math. 13 (2009) 211–224.

[18] L. Lovász and M.D. Plummer, Matching Theory, in: Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986).

[19] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162. https://doi.org/10.4064/cm-3-2-161-162

[20] Z. Shao and R. Solis-Oba, Labeling Mycielski graphs with a condition at distance two, Ars Combin. 140 (2018) 337–349.

[21] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922–931. https://doi.org/10.1090/S0002-9939-1953-0063009-7

[22] M.L. Vergnas, An extension of Tutte's 1-factor theorem, Discrete Math. 23 (1978) 241–255. https://doi.org/10.1016/0012-365X(78)90006-7

[23] D.B. West, Introduction to Graph Theory (2nd Edition, Prentice-Hall, Englewood Cliffs, NJ, 2001).

[24] R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217–1231. https://doi.org/10.1016/j.disc.2005.11.029