Graphs with equal independence and annihilation numbers

CE Larson, R Pepper - the electronic journal of combinatorics, 2011 - combinatorics.org
the electronic journal of combinatorics, 2011combinatorics.org
The annihilation number $ a $ of a graph is an upper bound of the independence number
$\alpha $ of a graph. In this article we characterize graphs with equal independence and
annihilation numbers. In particular, we show that $\alpha= a $ if, and only if, either (1) $
a\geq\frac {n}{2} $ and $\alpha'= a $, or (2) $ a<\frac {n}{2} $ and there is a vertex $ v\in V (G)
$ such that $\alpha'(Gv)= a (G) $, where $\alpha'$ is the critical independence number of the
graph. Furthermore, we show that it can be determined in polynomial time whether $\alpha …
Abstract
The annihilation number of a graph is an upper bound of the independence number of a graph. In this article we characterize graphs with equal independence and annihilation numbers. In particular, we show that if, and only if, either (1) and , or (2) and there is a vertex such that , where is the critical independence number of the graph. Furthermore, we show that it can be determined in polynomial time whether . Finally we show that a graph where is either König-Egerváry or almost König-Egerváry.
combinatorics.org
以上显示的是最相近的搜索结果。 查看全部搜索结果