






















In this paper, we study the average size of independent (vertex) sets of a graph. This invariant can be regarded as the logarithmic derivative of the independence polynomial evaluated at $1$. We are specifically concerned with extremal questions. The maximum and minimum for general graphs are attained by the empty and complete graph respectively, while for trees we prove that the path minimises the average size of independent sets and the star maximises it. While removing a vertex does not always decrease the average size of independent sets, we prove that there always exists a vertex for which this is the case.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。