In this paper we study the the average order of dominating sets in a graph, $\operatorname{avd}(G)$. Like other average graph parameters, the extremal graphs are of interest. Beaton and Brown (2021) conjectured that for all graphs $G$ of order $n$ without isolated vertices, $\operatorname{avd}(G) \leq 2n/3$. Recently, Erey (2021) proved the conjecture for forests without isolated vertices. In this paper we prove the conjecture and classify which graphs have $\operatorname{avd}(G) = 2n/3$.
翻译：在本文中, 我们用一个图表来研究占位单位的平均顺序, $\operatorname{avd} (G) $。 与其他平均图表参数一样, 极端图案也值得注意。 Beaton 和 Brown (2021年) 推测, 对于所有没有孤立的脊椎的图形, $\operatorname{avd} (G)\leq 2n/3$, $\leq 2n。 最近, Erey (2021年) 证明了没有孤立的脊椎的森林的预测。 在本文中, 我们证明了图表中含有$\opratorname{avd} (G) = 2n/3$的预测和分类 。
相关内容
微信扫码咨询专知VIP会员