论文标题
有效地识别具有相等独立性和歼灭数字的图形
Efficiently recognizing graphs with equal independence and annihilation numbers
论文作者
论文摘要
图$ g $的歼灭数字$ a（g）$是$ g $的独立数$α（g）$的有效计算上限。最近，希勒观察到，由于拉尔森和胡椒，$α（g）= a（g）$ g $的表征是错误的。由于识别这些图的已知有效算法是基于此特征的，因此识别图$ g $与$α（g）= a（g）$的复杂性再次被打开。我们证明这些图确实可以有效地识别。更普遍地，我们表明，使用$α（g）\ geq a（g） - \ ell $识别图形$ g $是使用$ \ ell $作为参数的固定参数。
The annihilation number $a(G)$ of a graph $G$ is an efficiently computable upper bound on the independence number $α(G)$ of $G$. Recently, Hiller observed that a characterization of the graphs $G$ with $α(G)=a(G)$ due to Larson and Pepper is false. Since the known efficient algorithm recognizing these graphs was based on this characterization, the complexity of recognizing graphs $G$ with $α(G)=a(G)$ was once again open. We show that these graphs can indeed be recognized efficiently. More generally, we show that recognizing graphs $G$ with $α(G)\geq a(G)-\ell$ is fixed parameter tractable using $\ell$ as parameter.
