Совершенные паросочетания в графах с предписанными локальными ограничениями

Иржавский П. А.; Орловичã Ю. Л.

Совершенные паросочетания в графах с предписанными локальными ограничениями

Иржавский П. А., Орловичã Ю. Л.

2019

https://doi.org/10.29235/1561-8323-2019-63-4-408-420

Граф называется K1,p-ограниченным (p ≥ 3), если для каждой вершины графа между любыми p ее соседями есть хотя бы p - 2 ребер. В работе устанавливаются достаточные условия существования совершенного паросочетания в K1,p -ограниченных графах. Из этих условий, в частности, вытекает классический результат Ю. Петерсена о том, что в любом реберно 2-связном 3-регулярном графе существует совершенное паросочетание.

Иржавский П. А., Орловичã Ю. Л. Совершенные паросочетания в графах с предписанными локальными ограничениями. Доклады Национальной академии наук Беларуси. 2019;63(4):408-420. https://doi.org/10.29235/1561-8323-2019-63-4-408-420

Цитирование

Список литературы

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.

Источник

Информация

Автор

Иржавский П. А. Белорусский государственный университет
Орловичã Ю. Л. Белорусский государственный университет

Страницы

408-420

Год издания

2019

Ключевые слова

Коллекции

Доклады Национальной академии наук Беларуси