

























Let $α(G)$ denote the cardinality of a maximum independent set, while $μ(G)$ be the size of a maximum matching in the graph $G=\left(V,E\right) $. If $α(G)+μ(G)=\left\vert V\right\vert $, then $G$ is a König-Egerváry graph. If $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$ is the degree sequence of $G$, then the annihilation number $h\left(G\right) $ of $G$ is the largest integer $k$ such that $\sum\limits_{i=1}^{k}d_{i}\leq\left\vert E\right\vert $ (Pepper 2004, Pepper 2009). A set $A\subseteq V$ satisfying $\sum \limits_{a\in A} deg(a)\leq\left\vert E\right\vert $ is an annihilation set, if, in addition, $ deg\left(v\right) +\sum\limits_{a\in A} deg(a)>\left\vert E\right\vert $, for every vertex $v\in V(G)-A$, then $A$ is a maximal annihilation set in $G$. In (Larson & Pepper 2011) it was conjectured that the following assertions are equivalent: (i) $α\left(G\right) =h\left(G\right) $; (ii) $G$ is a König-Egerváry graph and every maximum independent set is a maximal annihilating set. In this paper, we prove that the implication "(i) $\Longrightarrow$ (ii)" is correct, while for the opposite direction we provide a series of generic counterexamples. Keywords: maximum independent set, matching, tree, bipartite graph, König-Egerváry graph, annihilation set, annihilation number.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。