Preview

Doklady of the National Academy of Sciences of Belarus

Advanced search

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.

Views: 792


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)