Minimum Number of Vertices of Graphs without Perfect Matching, with Given Edge Connectivity and Minimum and Maximum Degrees

摘要

A matching M in a graph G is a subset of E(G) in which no two edges have a vertex in common. A vertex V is unsaturated by M if there is no edge of M is incident with v. A matching M is called a perfect matching if there is no vertex of the graph is unsaturated by M. Let G be a K-edge-connected graph, k≥1, on even n vertices, have minimum degree r and maximum degree r+e, e≥1. In this paper we find a lower bound for n when G has no perfect matchings.