Article in volume
Authors:
Kamal Dliou
National School of Applied Sciences(ENSA), Ibn Zohr University.
email: dlioukamal@gmail.com
Hicham El Boujaoui
National School of Applied Sciences(ENSA), Ibn Zohr University.
email: h.elboujaoui@uiz.ac.ma
Mustapha Kchikech
Modeling and combinatorial laboratory, polydisciplinary faculty of Safi.
email: m.kchikech@uca.ac.ma
Title:
$L(2,1)$-labeling of the iterated Mycielski graphs of graphs and some problems related to matching problems
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 489-518
Received: 2021-08-29 , Revised: 2022-04-20 , Accepted: 2022-04-21 , Available online: 2022-05-16 , https://doi.org/10.7151/dmgt.2457
Abstract:
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\geq 1$,
we give sharp bounds for $\lambda(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 $\bigtriangleup$, and $\lambda(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
$\lambda(M(G))$ the $L(2, 1)$-labeling number of the Mycielski graph 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 \lambda(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 graph and the iterated Mycielski graph of some
graph classes.
Keywords:
frequency assignment, $L(2,1)$-labeling, Mycielski construction, matching
References:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - W.K. Hale, Frequency assignment: Theory and applications, {Proc. IEEE } 68 (1980) 1497–1514.
https://doi.org/10.1109/PROC.1980.11899 - 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.
- 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 - 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 - 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 - W. Lin and P.C.B. Lam, Star matching and distance two labelling, Taiwanese J. Math. 13 (2009) 211–224.
- L. Lovász and M.D. Plummer, Matching Theory, in: Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986).
- J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162.
https://doi.org/10.4064/cm-3-2-161-162 - Z. Shao and R. Solis-Oba, Labeling Mycielski graphs with a condition at distance two, Ars Combin. 140 (2018) 337–349.
- 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 - 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 - D.B. West, Introduction to Graph Theory (2nd Edition, Prentice-Hall, Englewood Cliffs, NJ, 2001).
- 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
Close