论文标题
Wiener索引在给定的最低度和最高度的图表中
Wiener index in graphs with given minimum degree and maximum degree
论文作者
论文摘要
让$ g $是订单$ n $的连接图。$ g $的维纳指数$ w（g）$ of $ g $是所有无订购的$ g $的顶点之间的距离之和。在本文中，我们表明众所周知的上限$ \ big（\ frac {n} {δ+1}+1} +2 \ big）{n \ select 2} $在订单$ n $和最低度$δ$的Wiener索引上Kouider，P。Winkler，平均距离和最低度。 J.图形第25号1（1997）]如果该图还包含一个大程度的顶点，则可以显着改善。具体而言，我们给出了渐近尖锐的$ w（g）\ leq {n-δ+δ\选择2} \ frac {n+2δ} {δ+1}+1}+2n（n-1）$ thagral $ g $ g $ n $ n $ n $，最小值$ $ $δ$ $δ$和最大$δ$和最大$δ$ $ g $ g $ g $ g $。我们证明了无三角形图的结果相似，并且确定了给定订单，最低和最高度的Wiener索引上的一个绑定，从某种意义上说，这是最好的。
Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. In this paper we show that the well-known upper bound $\big( \frac{n}{δ+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $δ$ [M. Kouider, P. Winkler, Mean distance and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved significantly if the graph contains also a vertex of large degree. Specifically, we give the asymptotically sharp bound $W(G) \leq {n-Δ+δ\choose 2} \frac{n+2Δ}{δ+1}+ 2n(n-1)$ on the Wiener index of a graph $G$ of order $n$, minimum degree $δ$ and maximum degree $Δ$. We prove a similar result for triangle-free graphs, and we determine a bound on the Wiener index of $C_4$-free graphs of given order, minimum and maximum degree and show that it is, in some sense, best possible.
