|
|||||
|
|
The extreme set condition of a graph |
|
| Authors: | Shiying Wang Jianxiu Hao |
| Affiliation: | a Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, Hubei, People's Republic of China b Department of Mathematics, Shanxi University, Taiyuan 030006, People's Republic of China c Department of Mathematics, Zhejiang Normal University, Jinhua 321004, People's Republic of China |
| Abstract: | 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 i2. 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 i2. 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 (1mi−1). (3) Let G be a connected simple graph containing an independent set of size i, where i2. 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 (1mi−1). |
| Keywords: | Extreme set Barrier Deficiency Independent set Matching |
| 本文献已被 ScienceDirect 等数据库收录！ | |