论文标题
王在极端树上定理的倒数结果
An inverse result for Wang's theorem on extremal trees
论文作者
论文摘要
在具有给定度序列的$ n $顶点的所有树中，我们如何最大化或最小化所有相邻的顶点$ x $和$ y $ f（\ mathrm {deg} x，\ mathrm {deg} y）$的总和？这里$ f $是满足“单调性”条件的固定对称函数\ [ f（x，a） + f（y，b）> f（y，a） + f（x，b）\ quad \ mbox {对于任何$ x> y $和$ a> b $}。 \]这些功能自然出现在图理论的几个领域，尤其是化学图理论。 王表明，所谓的“贪婪”树使这一数量最大化，而“交替的贪婪”树将其最小化。我们在本文中的目的是解决逆问题：我们精确地表征了这两个问题的最大树木。
Among all trees on $n$ vertices with a given degree sequence, how do we maximise or minimise the sum over all adjacent pairs of vertices $x$ and $y$ of $f(\mathrm{deg} x, \mathrm{deg} y)$? Here $f$ is a fixed symmetric function satisfying a 'monotonicity' condition that \[ f(x, a) + f(y, b) > f(y, a) + f(x, b) \quad \mbox{for any $x > y$ and $a > b$} . \] These functions arise naturally in several areas of graph theory, particularly chemical graph theory. Wang showed that the so-called 'greedy' tree maximises this quantity, while an 'alternating greedy' tree minimises it. Our aim in this paper is to solve the inverse problem: we characterise precisely which trees are extremal for these two problems.
