论文标题
关于消除序列之间的统治顺序
On the Domination Order among Elimination Sequences
论文作者
论文摘要
在1991年，Favaron，Mahéo和Saclé表明，残基被定义为当将Havel-Hakimi算法应用于度序列时剩余的零数，在任何图表序列的独立性上都产生了一个较低的界限。 1996年，Triesch通过引入消除序列简化和普遍了结果。克莱特曼（Kleitman）和王（Wang）在1973年证明了所有消除算法的所有图形序列，即以任何顺序划分的顶点，都保留了该序列是图形的，并以零序列终止。 现在，我们证明，在任何程度的序列中，源自Havel-Havel算法的消除序列占主导地位的所有其他消除序列。我们的结果意味着迈克尔·巴鲁斯（Michael Barrus）在2010年提出的猜想是：当迭代从图形序列中划出学位直到仅保留零的列表时，零的数量最多是该序列的残基。
In 1991, it was shown by Favaron, Mahéo, and Saclé that the residue, which is defined as the number of zeros remaining when the Havel-Hakimi algorithm is applied to a degree sequence, yields a lower bound on the independence number of any graph realising the sequence. In 1996, Triesch simplified and generalised the result by introducing elimination sequences. It was proved in 1973 by Kleitman and Wang that for any graphic sequence all elimination algorithms, i.e. laying-off vertices in any order, preserve that the sequence is graphic and terminate in a sequence of zeros. We now prove that for any degree sequence, the elimination sequence derived from the Havel-Havel algorithm dominates all other elimination sequences. Our result implies a conjecture posed by Michael Barrus in 2010: When iteratively laying off degrees from a graphic sequence until only a list of zeros remains, the number of zeros is at most the residue of this sequence.
