The extreme set condition of a graph Original Research Article

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c0(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c0(G−X)=def(G)+|X|. In this paper, we obtain the following: (1) Let G be a simple graph containing an independent set of size i, where i⩾2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G. (2) Let G be a connected simple graph containing an independent set of size i, where i⩾2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|⩾i, and |Γ(Y)|⩾|U|−i+m+1 for any Y ⊆ U, |Y|=m (1⩽m⩽i−1). (3) Let G be a connected simple graph containing an independent set of size i, where i⩾2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|⩾m+1 for any Y ⊆ U, |Y|=m (1⩽m⩽i−1).