Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

# L(2, 1)-Labeling of the Iterated Mycielski Graphs of Graphs and Some Problems Related to Matching Problems

###### Accepted: 21 Apr 2022
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

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 λ(Mt(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 2t−1(n + 2) − 2 ≤ λ(Mt(G)) ≤ 2t(n + 1) − 2. Thereafter, we characterize the graphs achieving the upper bound 2t(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 2t−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.

#### MSC 2010

[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-610.1016/0012-365X(82)90048-6 Search in Google Scholar

[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.234510.7151/dmgt.2345 Search in Google Scholar

[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/bxr03710.1093/comjnl/bxr037 Search in Google Scholar

[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-210.1016/S0012-365X(00)00261-2 Search in Google Scholar

[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-310.1016/S0012-365X(99)00033-3 Search in Google Scholar

[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/S089548019324533910.1137/S0895480193245339 Search in Google Scholar

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

[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-110.1016/S0166-218X(97)00126-1 Search in Google Scholar

[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-O10.1016/0012-365X(93)E0098-O Search in Google Scholar

[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.07510.1016/j.disc.2007.07.075 Search in Google Scholar

[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/040504810.1137/0405048 Search in Google Scholar

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

[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. Search in Google Scholar

[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.049710.1147/rd.45.0497 Search in Google Scholar

[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/021204010.1137/0212040 Search in Google Scholar

[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.319019031310.1002/jgt.3190190313 Search in Google Scholar

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

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

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

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

[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-710.1090/S0002-9939-1953-0063009-7 Search in Google Scholar

[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-710.1016/0012-365X(78)90006-7 Search in Google Scholar

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

[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.02910.1016/j.disc.2005.11.029 Search in Google Scholar

• #### A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD