|
Perfect matchings and $K_{1, p}$-restricted graphs
P. A. Irzhavski, Yu. L. Orlovich Belarusian State University, Minsk
Abstract:
A graph is called $K_{1, p}$-restricted ($p \ge 3$) if for every vertex of the graph there are at least $p - 2$ edges between any $p$ of its neighbours. We establish sufficient conditions for the existence of a perfect matching in $K_{1, p}$-restricted graphs in terms of their connectivity and vertex degrees. These conditions imply, in particular, the classical Petersen's result: any $2$-edge-connected $3$-regular graph contains a perfect matching.
Keywords:
$K_{1, p}$-restricted graph, strongly $K_{1, p}$-restricted graph, perfect matching, factor-critical graph.
Received: 23.11.2018 Revised: 07.02.2020
Citation:
P. A. Irzhavski, Yu. L. Orlovich, “Perfect matchings and $K_{1, p}$-restricted graphs”, Diskr. Mat., 32:1 (2020), 27–50; Discrete Math. Appl., 30:6 (2020), 391–408
Linking options:
https://www.mathnet.ru/eng/dm1550https://doi.org/10.4213/dm1550 https://www.mathnet.ru/eng/dm/v32/i1/p27
|
Statistics & downloads: |
Abstract page: | 295 | Full-text PDF : | 114 | References: | 32 | First page: | 17 |
|