RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2020 Volume 32, Issue 1, Pages 27–50 (Mi dm1550)

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.

UDC: 519.17

Received: 23.11.2018
Revised: 07.02.2020

DOI: 10.4213/dm1550


 English version:
Discrete Mathematics and Applications, 2020, 30:6, 391–408

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024