Perfect matchings in graphs with prescribed local restrictions
https://doi.org/10.29235/1561-8323-2019-63-4-408-420
Abstract
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.
About the Authors
Pavel A. Irzhavski
Belarusian State University
Belarus
Belarus
Irzhavski Pavel Aleksandrovich – Master of philosophy (Physics and Mathematics), Assistant of the Department
4, Nezavisimosti Ave., 220030, Minsk
Yury L. Orlovich
Belarusian State University
Belarus
Belarus
Orlovich Yury Leonidovich – Ph. D. (Physics and Mathematics), Associate professor, Head of the Department
4, Nezavisimosti Ave., 220030, Minsk
References
1. Lovasz L., Plummer M. D. Applied problems of graph theory. Theory of matchings in mathematics, physics and chemistry. Moscow, 1998. 653 p. (in Russian).
2. Plummer 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.059
3. Akiyama 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-1
4. yu Q. R., Liu G. Graph factors and matching extensions. Berlin, 2009. 353 p. https://doi.org/10.1007/978-3-540-93952-8
5. Li 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-8
6. Li 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.014
7. Wang J., Teng y. K1,p-restricted graphs. Adv. Math. (China), 2006, vol. 35, p. 657–662.
8. Wang 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
9. 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).
10. Ryjač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
11. Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on graph theory. Moscow, 1990. 384 p. (in Russian).
12. Petersen J. Die Theorie der regulären graphs. Acta Mathematica, 1891, vol. 15, p. 193–220 (in German). https://doi.org/10.1007/bf02392606
13. Tutte 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.107
14. yu Q. Characterizations of various matching extensions in graphs. Australasian Journal of Combinatorics, 1993, vol. 7, p. 55–64.
Review
Views: 784
Email this article 