danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2019-63-4-408-420dan-628Research ArticleИНФОРМАТИКАINFORMATICSСовершенные паросочетания в графах с предписанными локальными ограничениямиPerfect matchings in graphs with prescribed local restrictionsИржавскийП. А.IrzhavskiPavel A.

Иржавский Павел Александрович – магистр, ассистент кафедры

пр. Независимости, 4, 220030, Минск

Irzhavski Pavel Aleksandrovich – Master of philosophy (Physics and Mathematics), Assistant of the Department

4, Nezavisimosti Ave., 220030, Minsk

irzhavski@bsu.byОрловичãЮ. Л.OrlovichYury L.

Орлович Юрий Леонидович – канд. физ.-мат. наук, доцент, заведующий кафедрой

пр. Независимости, 4, 220030, Минск

Orlovich Yury Leonidovich – Ph. D. (Physics and Mathematics), Associate professor, Head of the Department

4, Nezavisimosti Ave., 220030, Minsk

orlovich@bsu.byБелорусский государственный университетBelarusian State University201912092019634408420Copyright © Иржавский П.А., Орловичã Ю.Л., 20192019Иржавский П.А., Орловичã Ю.Л.Irzhavski P.A., Orlovich Y.L.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/628

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

A graph is called K1,p-restricted (p ≥ 3) if for every vertex of the graph there are at least p - 2 edges between any p neighbours of the vertex. In this article, new sufficient conditions for existence of a perfect matching in K1,p-restricted graphs are established. In particular, J. Petersen’s classical result that every 2-edge connected 3-regular graph contains a perfect matching follows from these conditions.

K1p-ограниченный графсильно K1p-ограниченный графсовершенное паросочетаниефакторно-критический графK1p-restricted graphstrongly K1p-restricted graphperfect matchingfactor-critical graphReferencesЛовас, Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М., 1998. – 653 с.Lovasz L., Plummer M. D. Applied problems of graph theory. Theory of matchings in mathematics, physics and chemistry. Moscow, 1998. 653 p. (in Russian).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.059Plummer M. D. Graph factors and factorization: 1985–2003: A survey. Discrete Mathematics, 2007, vol. 307, no. 7–8, pp. 791–821. https://doi.org/10.1016/j.disc.2005.11.059Akiyama, 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-1Akiyama J., kano M. Factors and factorizations of graphs. Proof techniques in factor theory. Lecture Notes in Mathematics. Vol. 2031. Berlin, 2011. 353 p. https://doi.org/10.1007/978-3-642-21919-1yu 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-8yu Q. R., Liu G. Graph factors and matching extensions. Berlin, 2009. 353 p. https://doi.org/10.1007/978-3-540-93952-8Li, 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-8Li R., Schelp R. H. Hamiltonicity of {K1,4, K1,4 + e}-free graphs. Discrete Mathematics, 2002, vol. 245, no. 1–3, p. 195–202. https://doi.org/10.1016/s0012-365x(01)00141-8Li, 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.014Li R. Hamiltonicity of 2-connected {K1,4, K1,4 + e}-free graphs. Discrete Mathematics, 2004, vol. 287, p. 69–76. https://doi.org/10.1016/j.disc.2004.05.014Wang, J. K1,p-restricted graphs / J. Wang, y. Teng // Adv. Math. (China). – 2006. – Vol. 35. – P. 657–662.Wang J., Teng y. K1,p-restricted graphs. Adv. Math. (China), 2006, vol. 35, p. 657–662.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.035Wang J., Li M. Fully cycle extendability of K1,4-restricted graphs. Discrete Mathematics, 2009, vol. 309, p. 4011–4016. https://doi.org/10.1016/j.disc.2008.11.035Иржавский, П. А. Полная циклическая расширяемость локально связных K1,4-ограниченных графов / П. А. Иржавский, Ю. Л. Орлович // Тр. Ин-та математики НАН Беларуси. – 2012. – Т. 20, № 2. – С. 36–50.Irzhavski P. A., Orlovich yu. L. Full cycle extendability of locally connected K1,4-restricted graphs. Trudy Instituta matematiki [Proceedings of the Institute of Mathematics], 2012, vol. 20, no. 2, p. 36–50 (in Russian).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.006Ryjaček Z., Vrana P., Wang Sh. Closure for {K1,4, K1,4 + e}-free graphs. Journal of Combinatorial Theory, Series B, 2019, vol. 134, p. 239–263. https://doi.org/10.1016/j.jctb.2018.06.006Лекции по теории графов / В. А. Емеличев [и др.]. – М., 1990. – 384 с.Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on graph theory. Moscow, 1990. 384 p. (in Russian).Petersen, J. Die Theorie der regulären graphs / J. Petersen // Acta Math. – 1891. – Vol. 15. – P. 193–220. https://doi.org/10.1007/bf02392606Petersen J. Die Theorie der regulären graphs. Acta Mathematica, 1891, vol. 15, p. 193–220 (in German). https://doi.org/10.1007/bf02392606Tutte, 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.107Tutte W. T. The factorization of linear graphs. Journal of the London Mathematical Society, 1947, vol. s1–22, no. 2, p. 107–111. https://doi.org/10.1112/jlms/s1-22.2.107yu, Q. Characterizations of various matching extensions in graphs / Q. yu // Australas. J. Comb. – 1993. – Vol. 7. – P. 55–64.yu Q. Characterizations of various matching extensions in graphs. Australasian Journal of Combinatorics, 1993, vol. 7, p. 55–64.

The authors declare that there are no conflicts of interest present.