Совершенные паросочетания в графах с предписанными локальными ограничениями
https://doi.org/10.29235/1561-8323-2019-63-4-408-420
Аннотация
Граф называется K1,p-ограниченным (p ≥ 3), если для каждой вершины графа между любыми p ее соседями есть хотя бы p - 2 ребер. В работе устанавливаются достаточные условия существования совершенного паросочетания в K1,p -ограниченных графах. Из этих условий, в частности, вытекает классический результат Ю. Петерсена о том, что в любом реберно 2-связном 3-регулярном графе существует совершенное паросочетание.
Об авторах
П. А. Иржавский
Белорусский государственный университет
Беларусь
Беларусь
Иржавский Павел Александрович – магистр, ассистент кафедры
пр. Независимости, 4, 220030, Минск
Ю. Л. Орловичã
Белорусский государственный университет
Беларусь
Беларусь
Орлович Юрий Леонидович – канд. физ.-мат. наук, доцент, заведующий кафедрой
пр. Независимости, 4, 220030, Минск
Список литературы
1. Ловас, Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М., 1998. – 653 с.
2. Plummer, M. D. Graph factors and factorization: 1985–2003: A survey / M. D. Plummer // Discrete Math. – 2007. – Vol. 307, N 7–8. – P. 791–821. https://doi.org/10.1016/j.disc.2005.11.059
3. Akiyama, J. Factors and factorizations of graphs. Proof techniques in factor theory / J. Akiyama, M. kano. – Berlin, 2011. – Vol. 2031. – 353 p. https://doi.org/10.1007/978-3-642-21919-1
4. yu Q. R. Graph factors and matching extensions / Q. R. yu, G. Liu. – Berlin, 2009. – 353 p. https://doi.org/10.1007/978-3-540-93952-8
5. Li, R. Hamiltonicity of {K1,4, K1,4 + e}-free graphs / R. Li, R. H. Schelp // Discrete Math. – 2002. – Vol. 245, N 1–3. – P. 195–202. https://doi.org/10.1016/s0012-365x(01)00141-8
6. Li, R. Hamiltonicity of 2-connected {K1,4, K1,4 + e}-free graphs / R. Li // Discrete Math. – 2004. – Vol. 287, N 1–2. – P. 69–76. https://doi.org/10.1016/j.disc.2004.05.014
7. Wang, J. K1,p-restricted graphs / J. Wang, y. Teng // Adv. Math. (China). – 2006. – Vol. 35. – P. 657–662.
8. Wang, J. Fully cycle extendability of K1,4-restricted graphs / J. Wang, M. Li // Discrete Math. – 2009. – Vol. 309, N 12. – P. 4011–4016. https://doi.org/10.1016/j.disc.2008.11.035
9. Иржавский, П. А. Полная циклическая расширяемость локально связных K1,4-ограниченных графов / П. А. Иржавский, Ю. Л. Орлович // Тр. Ин-та математики НАН Беларуси. – 2012. – Т. 20, № 2. – С. 36–50.
10. Ryjaček, Z. Closure for {K1,4, K1,4 + e}-free graphs / Z. Ryjaček, P. Vrana, Sh. Wang // J. Combin. Theory Ser. B. – 2019. – Vol. 134. – P. 239–263. https://doi.org/10.1016/j.jctb.2018.06.006
11. Лекции по теории графов / В. А. Емеличев [и др.]. – М., 1990. – 384 с.
12. Petersen, J. Die Theorie der regulären graphs / J. Petersen // Acta Math. – 1891. – Vol. 15. – P. 193–220. https://doi.org/10.1007/bf02392606
13. Tutte, W. T. The factorization of linear graphs / W. T. Tutte // J. London Math. Soc. – 1947. – Vol. s1–22, N 2. – P. 107–111. https://doi.org/10.1112/jlms/s1-22.2.107
14. yu, Q. Characterizations of various matching extensions in graphs / Q. yu // Australas. J. Comb. – 1993. – Vol. 7. – P. 55–64.
Рецензия
Просмотров: 780
Послать статью по эл. почте 