论文标题
在树的独立集序列上
On the independent set sequence of a tree
论文作者
论文摘要
Alavi，Malde，Schwenk和Erds询问了每棵树的独立集序列是否是单峰的。在这里，我们对这个问题进行了一些观察。我们表明，对于均匀的随机树（标记）树，几乎肯定（A.A.S.）渐近（a.a.s.）最初约49.5％的序列正在增加，而终端约为38.8％。我们的方法使用矩阵树定理，结合了计算。我们还介绍了Levit和Mandrescu结果的概括，这是关于König-Egerváry图的独立集序列的最后三分之一。
Alavi, Malde, Schwenk and Erdős asked whether the independent set sequence of every tree is unimodal. Here we make some observations about this question. We show that for the uniformly random (labelled) tree, asymptotically almost surely (a.a.s.) the initial approximately 49.5\% of the sequence is increasing while the terminal approximately 38.8\% is decreasing. Our approach uses the Matrix Tree Theorem, combined with computation. We also present a generalization of a result of Levit and Mandrescu, concerning the final one-third of the independent set sequence of a König-Egerváry graph.
