Combinatorial properties of the family of maximum stable sets of a graph
Combinatorial properties of the family of maximum stable sets of a graph
复制标题
图的最大稳定集族的组合性质
DOI：
10.1016/s0166-218x(01)00183-4
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Eugen Mandrescu
中科院分区：
文献类型：
--
作者：
Vadim E. Levit;Eugen Mandrescu
图G的稳定数α(G)是图G的最大稳定集的大小，核(G)=⋂{S：S是最大稳定集}，ξ(G)=|核(G)|。本文证明了对图G：(I)如果G没有孤立顶点，且ξ(G)⩽1，则G是拟正则的；(Ii)如果G的阶为n，且α(G)>；(n+k−min{1，|N(⩾(G)|}))/2，对某个kξ1，则⩾(G)k+1；此外，如果n+k−min{1，|N(核(G))|}是偶数，则ξ(G)⩾k+2.最后一个发现是对Hammer，Hansen和Simeone的一个结果的加强，该结果指出：当ξ(G)⩾1为α(G)>；n/2时，对于König-Egerváry图，即对于满足等式α(G)+μ(G)=n的图，我们证明了|μ(G)是G的一个匹配的最大长.|N(核(G))|是α(G)>；n/2的充要条件。此外，对于无孤立点的二部图，ξ(G)⩾2等价于α(G)>；n/2。我们还证明了霍尔结婚定理对于König-Egerváry图是成立的，并且只对一个特定的稳定集检验Hall条件就足够了，即对于核(G)。
The stability numberα(G) of a graph G is the size of a maximum stable set of G, core(G)=⋂{S : S is a maximum stable set inG}, and ξ(G)=|core(G)|. In this paper we prove that for a graph G the following assertions are true: (i) if G has no isolated vertices, and ξ(G)⩽1, then G is quasi-regularizable; (ii) if the order of G is n, and α(G)>(n+k−min{1,|N(core(G))|})/2, for some k⩾1, then ξ(G)⩾k+1; moreover, if n+k−min{1,|N(core(G))|} is even, then ξ(G)⩾k+2. The last finding is a strengthening of a result of Hammer, Hansen, and Simeone, which states that ξ(G)⩾1 is true whenever α(G)>n/2. In the case of König–Egerváry graphs, i.e., for graphs enjoying the equality α(G)+μ(G)=n, where μ(G) is the maximum size of a matching of G, we prove that |core(G)|>|N(core(G))| is a necessary and sufficient condition for α(G)>n/2. Furthermore, for bipartite graphs without isolated vertices, ξ(G)⩾2 is equivalent to α(G)>n/2. We also show that Hall's Marriage Theorem is true for König–Egerváry graphs, and, it is sufficient to check Hall's condition only for one specific stable set, namely for core(G).