树的第五小至第七小度距离

The Fifth to Seventh Minimal Degree Distance of the Tree

摘要: 图的度距离指标是图的每一个点的度与这个点到图G的所有点的距离乘积的和。何秀萍给出了n阶树中具有第一小至第四小度距离的树，并确定了其度距离。本文在对以上结果认真研究的基础上，借助图的变换，应用计算递归，研究了n阶树T_n的度距离排序问题，确定了这个序中的第五小至第七小的树，并且给出了相应的度距离。

Abstract: The degree distance indicator of the graph is the sum of the degrees of each point of the graph and the distance between the point and all points of the graph. The tree with the first small to fourth small distance in the order tree is given by He Xiuping, and its degree distance is determined. Based on the careful study of the above results, this paper studies the degree distance sorting problem of the order tree T_n by using the transformation of the graph, and determines the fifth small to seventh tree in this order, and gives the corresponding degree distance.

1. 引言

图论是数学中的一个比较年轻的分支，但在最近几十年中，图论本身及其应用研究都得到了迅猛的发展 [1] [2] 。图G的度距离是由Dobrynin和Kochetova [3] 及Gutman [4] 在1994年引入的一种新的拓扑指标，之后很多数学家对这种指标进行了研究 [5] - [12] 。

本文考虑的图都是有限、无向的简单图。如果一个图的顶点数和边数都是有限的，那么我们就称这个图为有限图。一个简单图是指：这个图中没有环，并且没有两条边的端点是完全相同的。设 $G=\left(V,E\right)$ 是一个n阶无向简单图， $V\left(G\right)$ 和 $E\left(G\right)$ 分别表示图的顶点集和边集， $\left|V\left(G\right)\right|=n$ 和 $\left|E\left(G\right)\right|=m$ 分别表示图的顶点数和边数。 $G-v$ 是指在图G中删掉点v及与它关联的边得到的图。图G中顶点u的度 [13] 指的是在图G中与点u关联的所有边的条数，记作 ${\mathrm{deg}}_G\left(u\right)$，简写为 $\mathrm{deg}\left(u\right)$。且

${\displaystyle {\sum }_{u\in V\left(G\right)}\mathrm{deg}\left(u\right)}=2m$

下面给出图G的度距离的定义：

定义 [14] ：若 $u,v\in V\left(G\right)$，则 $u,v$ 间的距离 $d\left(u,v\right)$ 指的是连接 $u,v$ 的最短路的长度，则

$D^{\prime }\left(G\right)={\displaystyle {\sum }_{u\in V\left(G\right)}\mathrm{deg}\left(u\right)D\left(u|G\right)}$

被称为图G的度距离。其中 $\mathrm{deg}\left(u\right)$ 是顶点u在图G中的度， $D\left(u|G\right)$ 是顶点u到G中所有顶点的距离之和，即

$D\left(u|G\right)={\displaystyle {\sum }_{v\in V\left(G\right)}d\left(u,v\right)}$。

我们把度为1的点称为图G的悬挂点，与悬挂点相连的边称为悬挂边。本文中我们用 $T_n$ 表示具有n个顶点的树，现对 $T_n$ 作如下划分，第一种划分： $T_n={\displaystyle \underset{i=1}{\overset{n-3}{\cup }}{T}_n^{\left(i\right)}}$，且当 $i\ne j$ 时 $T_n^{\left(i\right)}\cap T_n^{\left(j\right)}=\varphi$，其中 $T_n^{\left(i\right)}$ 表示恰有i条悬挂边的n阶树的集合，即在路 $P_{i+1}$ 的顶点 $x_1,x_2,\cdots ,x_{i+1}$ 上粘上一些悬挂点得到的图。则 $T_n^{\left(0\right)}=\left\{K_{1,n-1}\right\}$， $T_n^{\left(n-3\right)}=\left\{P_n\right\}$。第二种划分： $T_n={\displaystyle \underset{i=2}{\overset{n-1}{\cup }}{T}_n^i}$，且当 $i\ne s$ 时 $T_n^i\cap T_n^s=\varphi$，其中 $T_n^i$ 表示恰有i条悬挂边的n阶树的集合，易知星图 $K_{1,n-1}$ 为具有最多悬挂边的唯一树，悬挂边数为 $n-1$ ；路 $P_n$ 是具有最少悬挂边的唯一树，悬挂边数为2，即 $T_n^{n-1}=\left\{K_{1,n-1}\right\}$， $T_n^2=\left\{P_n\right\}$。

本文在文献 [9] 的基础上，借助图的变换，继续讨论n阶树 $T_n$ 的度距离排序问题，刻画了这个序中从第五小至第七小的树，并且给出了相应的度距离。

2. 预备知识

引理1 [9] ：设G，H为图1所示的两个n阶连通图，T和U是其连通子图。则有

$D^{\prime }\left(H\right)>D^{\prime }\left(G\right)$。

Figure 1. Graphs G and H

图1. 图G和H

定义1 [9] ：设 $T\in T_n$， $n\ge 4$， $e=uv$ 是T的一条非悬挂边， $T_1$ 和 $T_2$ 是 $T\backslash e$ 的2个分支， $u\in T_1$ , $v\in T_2$。T的一个长边变换是指对T的如下变换：给树T在u处添加一条悬挂边，再将边e收缩后得到的一个新的n阶树 $T_0$，如图2。

Figure 2. Tree T and T₀

图2. 树T和T₀

推论1 [9] ： $T\in T_n$， $n\ge 4$，并且T有非悬挂边，令 $T_0$ 是T经过一次长边变换后所得的树，则 $D^{\prime }\left(T\right)>D^{\prime }\left(T_0\right)$。

由推论1可知，对树作长边变换，它的度距离严格减小。根据引理1.1，树的非悬挂边越少，其度距离就越小。由此可以确定具有较小度距离的树一定会在这样的树中取得：设 $T_{n,s_1,s_2,\cdots ,s_{i+1}}^{\left(i\right)}\in T_n^{\left(i\right)}$， $s_1,s_{i+1}\ge 1$ 且 $s_2,\cdots ,s_i\ge 0$，树 $T_{n,s_1,s_2,\cdots ,s_{i+1}}^{\left(i\right)}$ 是在路 $P_{i+1}$ 的两个端点分别粘上 $s_1$ 和 $s_{i+1}$ 个悬挂点，在路的其它点上分别粘上 $s_2,\cdots ,s_i$ 个悬挂点得到的n阶树的集合。特别地，当 $i=1$ 时， $T_{n,s_1,s_2}^{\left(1\right)}$ 简记为 $T_{n,i}^{\left(1\right)}$ ( $i=s_1$)，当 $i=2$ 时， $T_{n,s_1,s_2,s_3}^{\left(2\right)}$ 简记为 $T_{n,i,j}^{\left(2\right)}$ ( $i=s_1,j=s_3$), 当 $i=3$ 时， $T_{n,s_1,s_2,s_3,s_4}^{\left(3\right)}$ 简记为 $T_{k,i,l,j}^{\left(3\right)}$ ( $i=s_1,j=s_4,k=s_2,l=s_3$)，当 $i=4$ 时， $T_{n,s_1,s_2,s_3,s_4,s_5}^{\left(4\right)}$ 简记为 $T_{k,i,l,m,j}^{\left(4\right)}$ ( $i=s_1,k=s_2,l=s_3,m=s_4,j=s_5$)。

引理2 [6] ：图 $G_{r,s}$ 的结构如图3所示，令 $\left|V\left(G\right)\right|=m$，则当 $r+m\ge s\ge 1$ 时，有

Figure 3. Graphs G_r,s and H_r,s

图3. 图G_r,s和H_r,s

$D^{\prime }\left(G_{r,s}\right)>D^{\prime }\left(G_{r+1,s-1}\right)$

其中G是单圈图。

特别地，当G是树T时，有：

推论2： $T_{r,s}$ 如图3所示，令 $\left|V\left(T\right)\right|=m\left(m\ge 2\right)$，则

(1) 当 $r+m\ge s\ge 1$ 时，有 $D^{\prime }\left(T_{r,s}\right)\ge D^{\prime }\left(T_{r+1,s-1}\right)$ ；

(2) 当 $r+m<s$ 时，有 $D^{\prime }\left(T_{r,s}\right)<D^{\prime }\left(T_{r+1,s-1}\right)$。

证明：将 $T_{r,s}$ 分为 $T-v$，点v、w， $$ 个孤立点等部分，根据图的度距离的定义

$D^{\prime }\left(G\right)={\displaystyle {\sum }_{u\in V\left(G\right)}\mathrm{deg}\left(u\right)D\left(u|G\right)}$

有

$\begin{array}{c}{D}^{\prime }\left(T_{r,s}\right)={\displaystyle {\sum }_{u\in V\left(T_{r,s}\right)}\mathrm{deg}\left(u\right)D\left(u|T_{r,s}\right)}\\ =s\left[2s+3r+2m+D\left(v|T\right)-1\right]+r\left[2r+3s+m+D\left(v|T\right)\right]\\ +\left(s+1\right)\left[s+2r+m+D\left(v|T\right)\right]+\left[{\mathrm{deg}}_T\left(v\right)+\left(r+1\right)\right]\left[r+2s+1+D\left(v|T\right)\right]\\ +{\displaystyle {\sum }_{x\in V\left(T\right)-v}\mathrm{deg}\left(x\right)\left[D\left(v|T\right)+rD\left(x|v\right)+r+sD\left(x|v\right)+2s+D\left(x|v\right)+1\right]}\\ =3{\left(s+r\right)}^2+4sr+3ms+mr+2\left(s+r+1\right)D\left(x|v\right)+2s+4r+m\\ +\left(r+2s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}+D^{\prime }\left(T\right)+\left(r+s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)-v}D\left(x|v\right)}\end{array}$

$\begin{array}{c}{D}^{\prime }\left(T_{r+1,s-1}\right)=3{\left(s+r\right)}^2+4sr+3ms+mr+2\left(s+r+1\right)D\left(x|v\right)+2s+4r+m+D^{\prime }\left(T\right)\\ +\left(r+s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)-v}D\left(x|v\right)}+\left(r+2s\right){\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}+4s-4r-2m-2\end{array}$

其中， ${\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}=2\left(m-1\right)$ 则

$\begin{array}{c}{D}^{\prime }\left(T_{r+1,s-1}\right)-D^{\prime }\left(T_{r,s}\right)=4s-4r-2m-2-{\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}\\ =4s-4r-2m-2-2\left(m-1\right)\\ =4\left(s-r-m\right)\end{array}$

当 $r+m\ge s\ge 1$ 时，有 $D^{\prime }\left(T_{r,s}\right)\ge D^{\prime }\left(T_{r+1,s-1}\right)$ ；

当 $r+m<s$ 时，有 $D^{\prime }\left(T_{r,s}\right)<D^{\prime }\left(T_{r+1,s-1}\right)$。

由此结论可以得到：

推论3：当 $r+m\ge s\ge 1$ 时，有

$D^{\prime }\left(T_{r,s}\right)\ge D^{\prime }\left(T_{r+1,s-1}\right)\ge \cdots \ge D^{\prime }\left(T_{r+s+1,1}\right)$

推论4：当 $r+m<s$ 且 $m\ge 2$ 时，有

$D^{\prime }\left(T_{r+s-1,1}\right)<D^{\prime }\left(T_{1,r+s-1}\right)<\cdots <D^{\prime }\left(T_{r-1,s+1}\right)<D^{\prime }\left(T_{r,s}\right)$

当 $m\ge 3$ 时，有

$D^{\prime }\left(T_{r+s-1,1}\right)<D^{\prime }\left(T_{r+s-2,2}\right)\le D^{\prime }\left(T_{1,r+s-1}\right)<\cdots <D^{\prime }\left(T_{r-1,s+1}\right)<D^{\prime }\left(T_{r,s}\right)$

当 $m\ge 4$ 时，有

$D^{\prime }\left(T_{r+s-1,1}\right)<D^{\prime }\left(T_{r+s-2,2}\right)<D^{\prime }\left(T_{1,r+s-1}\right)<\cdots <D^{\prime }\left(T_{r-1,s+1}\right)<D^{\prime }\left(T_{r,s}\right)$

证明：当 $2\le r+m<s$ 时，由推论2 (2)知， $D^{\prime }\left(T_{1,r+s-1}\right)<\cdots <D^{\prime }\left(T_{r-1,s+1}\right)<D^{\prime }\left(T_{r,s}\right)$ 成立。

当 $m\ge 2$ 时，只需证 $D^{\prime }\left(T_{r+s-1,1}\right)<D^{\prime }\left(T_{1,r+s-1}\right)$ 成立。

当 $m\ge 3$ 时， $r+s+m-1>1$， $r+s+m-2\ge 2$， $D^{\prime }\left(T_{r+s-1,1}\right)<D^{\prime }\left(T_{r+s-2,2}\right)$ 成立。

所以要证结论成立，只需证明 $D^{\prime }\left(T_{r+s-2,2}\right)<D^{\prime }\left(T_{1,r+s-1}\right)$ 成立。由推论2知

$\begin{array}{c}{D}^{\prime }\left(T_{r,s}\right)=3{\left(s+r\right)}^2+4sr+3ms+mr+2\left(s+r+1\right)D\left(x|v\right)+2s+4r+m\\ +\left(r+2s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}+D^{\prime }\left(T\right)+\left(r+s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)-v}D\left(x|v\right)}\end{array}$

则

$\begin{array}{c}{D}^{\prime }\left(T_{1,r+s-1}\right)=3{\left(s+r\right)}^2+2\left(s+r+1\right)D\left(x|v\right)+D^{\prime }\left(T\right)+\left(r+s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)-v}D\left(x|v\right)}\\ +6r+6s+3ms+3mr-m-2+2\left(r+s\right){\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}(x)}\end{array}$

$\begin{array}{c}{D}^{\prime }\left(T_{r+s-2,2}\right)=3{\left(s+r\right)}^2+2\left(s+r+1\right)D\left(x|v\right)+D^{\prime }\left(T\right)+\left(r+s+1\right){\displaystyle {\sum }_{x\in V\left(T\right)-v}D\left(x|v\right)}\\ +12r+12s+ms+mr+5m-20+\left(r+s+3\right){\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}(x)}\end{array}$

其中 ${\displaystyle {\sum }_{x\in V\left(T\right)}\mathrm{deg}\left(x\right)}=2\left(m-1\right)$， $s\ge 3$ 且 $m\ge 2$，作差

$D^{\prime }\left(T_{1,r+s-1}\right)-D^{\prime }\left(T_{r+s-2,2}\right)=4\left(m-2\right)\left(r+s-3\right)$

故当 $m\ge 2$ 时，有 $4\left(m-2\right)\left(r+s-3\right)\ge 0$，即

$D^{\prime }\left(T_{1,r+s-1}\right)\ge D^{\prime }\left(T_{r+s-2,2}\right)$

当 $m\ge 3$ 时，有 $4\left(m-2\right)\left(r+s-3\right)>0$，即

$D^{\prime }\left(T_{1,r+s-1}\right)>D^{\prime }\left(T_{r+s-2,2}\right)$

命题得证。

定理1 [3] ：设 $T\in T_n$，则 $D^{\prime }\left(T\right)\ge 3n^2-7n+4$，等式成立当且仅当T是星图 $K_{1,n-1}$。

定理2 [9] ：对任意 $T_{n,i}^{\left(1\right)}$， $i\in \left[1,\left(n-2\right)/2\right]$，都有

$D^{\prime }\left(T_{n,1}^{\left(1\right)}\right)<D^{\prime }\left(T_{n,2}^{\left(1\right)}\right)<D^{\prime }\left(T_{n,3}^{\left(1\right)}\right)<\cdots <D^{\prime }(T_{n,\lfloor n/2\rfloor -1}^{(1))}$

其中 $D^{\prime }\left(T_{n,i}^{\left(1\right)}\right)=3n^2-7n+4-4{\left[i-\left(n-2\right)/2\right]}^2+{\left(n-2\right)}^2$。

定理3 [9] ： $T_{n,i,j}^{\left(2\right)}$ 中树的度距离由小开始的依次排序是 $T_{n,1,1}^{\left(2\right)},T_{n,2,1}^{\left(2\right)}$，其中 $D^{\prime }\left(T_{n,i,j}^{\left(2\right)}\right)=3n^2-7n+4-4{\left[i-\left(n-2\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2+2{\left(n-2\right)}^2$。

定理4 [9] ：树 $K_{1,n-1},T_{n,1}^{\left(1\right)},T_{n,2}^{\left(1\right)},T_{n,1,1}^{\left(2\right)}$ 是 $T_n$ 中度距离较小的前四个树，且

$D^{\prime }\left(K_{1,n-1}\right)<D^{\prime }\left(T_{n,1}^{\left(1\right)}\right)<D^{\prime }\left(T_{n,2}^{\left(1\right)}\right)<D^{\prime }(T_{n,1,1}^{(2))}$

3. 主要结果和证明

对 $\forall T\in T_n^{\left(i\right)}$，且 $i>3$，对T做 $i-3$ 次长边变换变成 $T^{\prime }$，使 $T^{\prime }\in T_n^{\left(3\right)}$。下面给出 $T_n^{\left(3\right)}$ 中度距离最小的树，然后对 $T_n$ 中的树排序。在图4中给出了 $T_n^{\left(3\right)}$ 中的两类图 $T_{k,i,l,j}^{\left(3\right)}$ 和 $R_{k,i,l,j}^{\left(3\right)}$，这些树的度距离的大小与 $k,i,l,m,j$ 的取值有关，这一部分回答了当 $k,i,l,m,j$ 分别取何值时 $T_{k,i,l,j}^{\left(3\right)}$， $R_{k,i,l,j}^{\left(3\right)}$ 的度距离取到最小值。

对 $T_{k,i,l,j}^{\left(3\right)}\in T_n^{\left(3\right)}$ 做推论2的变换，得到：

引理1：如图4所示，树 $T_{k,i,l,j}^{\left(3\right)}\in T_n^{\left(3\right)}$， $i,j\ge 1,k,l\ge 0$ 且 $i+j+k+l+4=n$，则

1) 当 $k+l+j+3\ge i$ 时，有 $D^{\prime }\left(T_{k,i,l,j}^{\left(3\right)}\right)\ge D^{\prime }\left(T_{k+1,i-1,l,j}^{\left(3\right)}\right)$。

Figure 4. Tree $T_{k,i,l,j}^{\left(3\right)}$ and $R_{k,i,l,j}^{(3)}$

图4. 树 $T_{k,i,l,j}^{\left(3\right)}$ 和 $R_{k,i,l,j}^{(3)}$

2) 当 $i>k+l+j+3$ 时，有 $D^{\prime }\left(T_{k,i,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{k+1,i-1,l,j}^{\left(3\right)}\right)$。

推论1：当 $k+l+j+3\ge i$， $i,j\ge 1,k,l\ge 0$ 且 $i+j+k+l+4=n$ 时，有

$D^{\prime }\left(T_{k,i,l,j}^{\left(3\right)}\right)\ge D^{\prime }\left(T_{k+1,i-1,l,j}^{\left(3\right)}\right)\ge \cdots \ge D^{\prime }(T_{k+i-1,1,l,j}^{(3))}$

根据推论4知：

推论2：当 $i>k+l+j+3$ 时， $i,j\ge 1,k,l\ge 0$ 且 $i+j+k+l+4=n$ 有

$D^{\prime }\left(T_{k+i-1,1,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{k+i-2,2,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{1,k+i-1,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{2,k+i-2,l,j}^{\left(3\right)}\right)<\dots <D^{\prime }(T_{k,i,l,j}^{(3))}$

由推论1和推论2得：

定理1：对任意的 $T_{k,i,l,j}^{\left(3\right)}\in T_n^{\left(3\right)}$，令 $s=k+i-1$，有 $D^{\prime }\left(T_{s,1,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{k,i,l,j}^{\left(3\right)}\right)$。

定理2：对树 $T_{s,1,l,j}^{\left(3\right)}$ ( $s,l\ge 0,j\ge 1$ 且 $s+l+j=n-5$)，当 $s=0,j=1$ 时， $T_{0,1,n-6,1}^{\left(3\right)}$ 度距离最小，且 $D^{\prime }\left(T_{0,1,n-6,1}^{\left(3\right)}\right)=3n^2+9n-52$。

证明： $T_{s,1,l,j}^{\left(3\right)}$ 结构如图5所示， $\mathrm{deg}\left(x_1\right)=2$， $\mathrm{deg}\left(x_2\right)=s+2$， $\mathrm{deg}\left(x_3\right)=l+2$， $\mathrm{deg}\left(x_4\right)=j+2$， $u\in V\left(T_{s,1,l,j}\right)-x_1-x_2-x_3-x_4$， $\mathrm{deg}\left(u\right)=1$。

Figure 5. Tree $T_{s,1,l,j\left(s=k+i-1\right)}^{\left(3\right)}$ $T_{s,1,t,1}^{\left(3\right)}$ and $R_{s,i,1,j}^{(3)}$

图5. 树 $T_{s,1,l,j\left(s=k+i-1\right)}^{\left(3\right)}$， $T_{s,1,t,1}^{\left(3\right)}$ 与 $R_{s,i,1,j}^{(3)}$

由

$D^{\prime }\left(G\right)={\displaystyle {\sum }_{u\in V\left(G\right)}\mathrm{deg}\left(u\right)D\left(u|G\right)}$

得

$D^{\prime }\left(T_{s,1,t,1}^{\left(3\right)}\right)=3{\left(s+l+j\right)}^2+31\left(s+l+j\right)+4sl+4lj+8sj+4l+16j+60$

又因为 $l=n-5-s-j$，所以

$\begin{array}{c}{D}^{\prime }\left(T_{s,1,l,j}^{\left(3\right)}\right)=3{\left(n-5\right)}^2+35\left(n-5\right)-4{\left[s-\left(n-6\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2\\ +{\left(n-2\right)}^2+{\left(n-6\right)}^2+60\end{array}$

因为n为常数， $$ 为整数，由二次函数性质知：当 $s=0,j=1$ 或 $s=n-6,j=1$ 时， (如图5)取得最小值 $3n^2+9n-52$，因为 $T_{0,1,n-6,1}^{\left(3\right)}$ 与 $T_{n-6,1,0,1}^{\left(3\right)}$ 同构，则具有最小度距离的树为 $T_{0,1,n-6,1}^{\left(3\right)}$。

定理3：在 $T_{k,i,l,j}^{\left(3\right)}$ 中有第一小至第五小度距离的树为：

$T_{0,1,n-6,1}^{\left(3\right)},T_{1,1,n-7,1}^{\left(3\right)},T_{0,1,n-7,2}^{\left(3\right)},T_{2,1,n-8,1}^{\left(3\right)},T_{1,1,n-8,2}^{\left(3\right)}\left(T_{0,2,n-7,1}^{\left(3\right)}\right)$。

证明：由推论2知， $D^{\prime }\left(T_{k+i-1,1,l,j}^{\left(3\right)}\right)<D^{\prime }\left(T_{k+i-2,2,l,j}^{\left(3\right)}\right)$， $T_{k+i-2,2,l,j}^{\left(3\right)}$ 记为 $T_{r,2,l,j}^{\left(3\right)}$，其中 $r=k+i-2$， $r+l+j+6=n$。由度距离的定义，有

$D^{\prime }\left(T_{r,2,l,j}^{\left(3\right)}\right)=3{\left(r+l+j\right)}^2+41\left(r+l+j\right)+4l\left(r+j+2\right)+8rj+24j+98$

把 $l=n-r-j-6$ 代入上式得，

$\begin{array}{c}{D}^{\prime }\left(T_{r,2,l,j}^{\left(3\right)}\right)=3{\left(n-6\right)}^2+41\left(n-6\right)-4{\left[r-(n-8)/2\right]}^2-4{\left[r-\left(n-2\right)/2\right]}^2\\ +{\left(n-8\right)}^2+{\left(n-2\right)}^2+8n+50\\ =3n^2+13n-88-4{\left[r-(n-8)/2\right]}^2-4{\left[r-\left(n-2\right)/2\right]}^2\\ +{\left(n-8\right)}^2+{\left(n-2\right)}^2\end{array}$

因为n是常数， $0\le r\le \left(n-8\right)/2,1\le j\le \left(n-2\right)/2$，由二次函数的性质知，当 $r=0,j=1$ 时， $T_{0,2,n-7,1}^{\left(3\right)}$ 是具有最小度距离的树，为 $D^{\prime }\left(T_{0,2,n-7,1}^{\left(3\right)}\right)=3n^2+17n-100$。

由定理2知，树 $T_{s,1,l,j}^{\left(3\right)}$ 的度距离大小与 $s,j$ 的取值有关，当 $0\le s\le \lfloor \left(n-6\right)/2\rfloor$， $1\le j\le \lfloor \left(n-2\right)/2\rfloor$ 时， $s,j$ 的取值越大， $T_{s,1,l,j}^{\left(3\right)}$ 的度距离就越大。考虑树的度距离大小，因为

$\begin{array}{c}{D}^{\prime }\left(T_{s,1,l,j}^{\left(3\right)}\right)=3{\left(n-5\right)}^2+35\left(n-5\right)-4{\left[s-\left(n-6\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2\\ +{\left(n-2\right)}^2+{\left(n-6\right)}^2+60\end{array}$

$D^{\prime }\left(T_{2,1,n-9,2}^{\left(3\right)}\right)=3n^2+21n-136$， $D^{\prime }\left(T_{1,1,n-7,1}^{\left(3\right)}\right)=3n^2+13n-80$， $D^{\prime }\left(T_{0,1,n-7,2}^{\left(3\right)}\right)=3n^2+13n-72$

$D^{\prime }\left(T_{2,1,n-8,1}^{\left(3\right)}\right)=3n^2+17n-116$， $D^{\prime }\left(T_{1,1,n-8,2}^{\left(3\right)}\right)=3n^2+17n-100$

由定理2， $D^{\prime }\left(T_{0,1,n-6,1}^{\left(3\right)}\right)=3n^2+9n-52$，所以当 $n\ge 11$ 时有，

$D^{\prime }\left(T_{0,1,n-6,1}^{\left(3\right)}\right)<D^{\prime }\left(T_{1,1,n-7,1}^{\left(3\right)}\right)<D^{\prime }\left(T_{0,1,n-7,2}^{\left(3\right)}\right)<D^{\prime }\left(T_{2,1,n-8,1}^{\left(3\right)}\right)<D^{\prime }\left(T_{1,1,n-8,2}^{\left(3\right)}\right)<D^{\prime }(T_{2,1,n-9,2}^{(3))}$

故在 $T_{k,i,l,j}^{\left(3\right)}$ 中有第一小至第五小度距离的树为：

$T_{0,1,n-6,1}^{\left(3\right)},T_{1,1,n-7,1}^{\left(3\right)},T_{0,1,n-7,2}^{\left(3\right)},T_{2,1,n-8,1}^{\left(3\right)},T_{1,1,n-8,2}^{(3)}$

由推论2有：

引理2： $R_{k,i,l,j}^{\left(3\right)}\in T_n^{\left(3\right)}$，如图4所示， $i,j,l\ge 1,k\ge 0$ 且 $i+j+k+l+4=n$，则

1) 当 $k+i+j+3\ge l$ 时，有 $D^{\prime }\left(R_{k,i,l,j}^{\left(3\right)}\right)\ge D^{\prime }\left(R_{k+1,i,l-1,j}^{\left(3\right)}\right)$。

2) 当 $l>k+i+j+3$ 时，有 $D^{\prime }\left(R_{k,i,l,j}^{\left(3\right)}\right)<D^{\prime }\left(R_{k+1,i,l-1,j}^{\left(3\right)}\right)$。

由引理2得：

推论4：当 $k+i+j+3\ge l$， $i,j,l\ge 1,k\ge 0$ 且 $i+j+k+l+4=n$ 时，有

$D^{\prime }\left(R_{k,i,l,j}^{\left(3\right)}\right)\ge D^{\prime }\left(R_{k+1,i,l-1,j}^{\left(3\right)}\right)\ge \cdots \ge D^{\prime }(R_{k+i-1,i,1,j}^{(3))}$

根据定理2有：

推论5：当 $l>k+i+j+3$， $i,j,l\ge 1,k\ge 0$ 且 $i+j+k+l+4=n$ 时，有

$D^{\prime }\left(R_{k+i-1,i,1,j}^{\left(3\right)}\right)<D^{\prime }\left(R_{k+i-2,i,2,j}^{\left(3\right)}\right)<D^{\prime }\left(R_{1,i,k+i-1,j}^{\left(3\right)}\right)<D^{\prime }\left(R_{2,i,k+i-2,j}^{\left(3\right)}\right)<\cdots <D^{\prime }(R_{k,i,l,j}^{(3))}$

定理4：对 $R_{k,i,l,j}^{\left(3\right)}\in T_n^{\left(3\right)}$，令 $s=k+l-1$，有 $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)<D^{\prime }\left(R_{k,i,l,j}^{\left(3\right)}\right)$。

定理5：树 $R_{s,i,1,j}^{\left(3\right)}$ ( $s\ge 0,i,j\ge 1,n\ge 5$， $s+i+j=n-5$)的度距离由小开始排序 $R_{n-7,1,1,1}^{\left(3\right)}$， $R_{n-8,2,1,1}^{\left(3\right)}$， $R_{n-9,2,1,2}^{\left(3\right)}$，且

$D^{\prime }\left(R_{n-7,1,1,1}^{\left(3\right)}\right)=3n^2+5n-32$， $D^{\prime }\left(R_{n-8,2,1,1}^{\left(3\right)}\right)=3n^2+9n-52$， $D^{\prime }\left(R_{n-9,2,1,2}^{\left(3\right)}\right)=3n^2+13n-72$。

证明： $R_{s,i,1,j}^{\left(3\right)}$ 如图5所示，由

$D^{\prime }\left(G\right)={\displaystyle {\sum }_{u\in V\left(G\right)}\mathrm{deg}\left(u\right)D\left(u|G\right)}$

得，

$D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)=3{\left(i+j+s\right)}^2+27\left(i+j+s\right)+4is+8ij+4sj+12i+12j+52$

把 $s=n-5-i-j$ 代入得

$D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)=3n^2-3n-8-4{\left[i-\left(n-2\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2+2{\left(n-2\right)}^2$

因为 $n\ge 5$ 为常数，当 $1\le i\le \left(n-2\right)/2$， $1\le j\le \left(n-2\right)/2$ 时，由二次函数的性质知： $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)$ 与 $s,j$ 的取值有关， $s,j$ 的取值越大， $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)$ 就越大.当 $i=j=1$ 时， $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)$ 取得最小值 $3n^2+5n-32$，则 $R_{s,i,1,j}^{\left(3\right)}$ 中度距离最小的树是 $R_{n-7,1,1,1}^{\left(3\right)}$ ；当 $i=2$， $j=1$ 或 $i=1$， $j=2$ 时， $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)$ 的值达到第二小，因为 $R_{n-8,2,1,1}^{\left(3\right)}\cong R_{n-8,1,1,2}^{\left(3\right)}$，则 $R_{n-8,2,1,1}^{\left(3\right)}$ 是 $R_{s,i,1,j}^{\left(3\right)}$ 中度距离第二小的树，度距离为 $3n^2+9n-52$ ；当 $i=2$， $j=2$ 时， $D^{\prime }\left(R_{s,i,1,j}^{\left(3\right)}\right)$ 的值达到第三小，即 $R_{n-9,2,1,2}^{\left(3\right)}$ 是 $R_{s,i,1,j}^{\left(3\right)}$ 中度距离第三小的树，度距离为 $3n^2+13n-72$。

定理6：在 $T_n^{\left(3\right)}$ 中第一小至第三小度距离的树为: $R_{n-7,1,1,1}^{\left(3\right)}$， $R_{n-8,2,1,1}^{\left(3\right)}$ ( $T_{0,1,n-6,1}^{\left(3\right)}$， $R_{n-8,1,2,1}^{\left(3\right)}$)， $R_{n-9,2,1,2}^{\left(3\right)}$。

证明：由推论4和推论5知： $R_{k+i-2,i,2,j}^{\left(3\right)}$ 即 $R_{p,i,2,j}^{\left(3\right)}$ ( $p=k+i-2$， $p+i+j+6=n$)是 $R_{k,i,l,j}^{\left(3\right)}$ 中度距离第二小的树，由度距离的定义：

$D^{\prime }\left(R_{p,i,2,j}^{\left(3\right)}\right)=3{\left(i+j+p\right)}^2+37\left(i+j+p\right)+4ip+8ij+4pj+16i+16j+86$

把 $p=n-6-i-j$ 代入上式得

$D^{\prime }\left(R_{p,i,2,j}^{\left(3\right)}\right)=3n^2+n-28-4{\left[i-\left(n-2\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2+2{\left(n-2\right)}^2$

因为 $n\ge 5$ 为常数，当 $1\le i\le \left(n-2\right)/2$， $1\le j\le \left(n-2\right)/2$ 时，由二次函数的性质知： $D^{\prime }\left(R_{p,i,2,j}^{\left(3\right)}\right)$ 跟 $i,j$ 的取值有关， $i,j$ 的取值越大， $D^{\prime }\left(R_{p,i,2,j}^{\left(3\right)}\right)$ 就越大。当 $i=j=1$ 时， $R_{n-8,1,2,1}^{\left(3\right)}$ 是具有最小度距离的树，且 $R_{n-8,1,2,1}^{\left(3\right)}\cong R_{n-8,2,1,1}^{\left(3\right)}\cong R_{n-8,1,1,2}^{\left(3\right)}$，度距离为 $3n^2+9n-52$ ；因树的对称性，当 $i=2$， $j=1$ 和 $i=1$， $j=2$ 时， $R_{n-9,2,2,1}^{\left(3\right)}\cong R_{n-9,1,2,2}^{\left(3\right)}\cong R_{n-9,2,1,2}^{\left(3\right)}$，度距离为 $3n^2+13n-72$， $R_{n-9,2,2,1}^{\left(3\right)}\left(R_{n-9,1,2,2}^{\left(3\right)},R_{n-9,2,1,2}^{\left(3\right)}\right)$ 是 $R_{p,i,2,j}^{\left(3\right)}$ 中有第二小的度距离的树。再由定理5， $R_{p,i,2,j}^{\left(3\right)}$ 中具有第一小至第三小的树是 $R_{n-7,1,1,1}^{\left(3\right)}$， $R_{n-8,2,1,1}^{\left(3\right)}$ ( $R_{n-8,1,2,1}^{\left(3\right)}$)， $R_{n-9,2,1,2}^{\left(3\right)}$ .由定理2知：在树 $T_{s,1,l,j}^{\left(3\right)}$ 中 $T_{0,1,n-6,1}^{\left(3\right)}$ 的度距离最小，其度距离为 $3n^2+9n-52$，故结论成立。

定理7：在 $T_n$ 中， $T_{n,3}^{\left(1\right)}$， $T_{n,2,1}^{\left(2\right)}$， $R_{n-7,1,1,1}^{\left(3\right)}$ 是具有第五小、第六小和第七小度距离的树，且

$D^{\prime }\left(T_{n,3}^{\left(1\right)}\right)=3n^2+5n-56$ , $D^{\prime }\left(T_{n,2,1}^{\left(2\right)}\right)=3n^2+5n-40$ , $D^{\prime }\left(R_{n-7,1,1,1}^{\left(3\right)}\right)=3n^2+5n-32$。

证明：由引理1及推论1可知 $T_n$ 中具有较小度距离的树在 $T_n^{\left(1\right)}$ 、 $T_n^{\left(2\right)}$ 和 $T_n^{\left(3\right)}$ 中。

由定理6，在 $T_n^{\left(3\right)}$ 中有第一小和第二小度距离的树为： $R_{n-7,1,1,1}^{\left(3\right)}$， $R_{n-8,2,1,1}^{\left(3\right)}$ ( $T_{0,1,n-6,1}^{\left(3\right)}$， $R_{n-8,1,2,1}^{\left(3\right)}$)。

要证结论成立，下面先比较 $T_n^{\left(1\right)}$ 、 $T_n^{\left(2\right)}$ 中的树与 $R_{n-7,1,1,1}^{\left(3\right)}$， $$ 的度距离的大小：

由定理2知，在 $T_n^{\left(1\right)}$ 中，

$D^{\prime }\left(T_{n,3}^{\left(1\right)}\right)=3n^2+5n-56,D^{\prime }\left(T_{n,4}^{\left(1\right)}\right)=3n^2+9n-92,D^{\prime }\left(T_{n,5}^{\left(1\right)}\right)=3n^2+13n-136$

由

$D^{\prime }\left(T_{n,i,j}^{\left(2\right)}\right)=3n^2-7n+4-4{\left[i-\left(n-2\right)/2\right]}^2-4{\left[j-\left(n-2\right)/2\right]}^2+2{\left(n-2\right)}^2$

得：

$D^{\prime }\left(T_{n,1,1}^{\left(2\right)}\right)=3n^2+n-20$， $D^{\prime }\left(T_{n,2,1}^{\left(2\right)}\right)=3n^2+5n-40$，

$D^{\prime }\left(T_{n,3,1}^{\left(2\right)}\right)=3n^2+9n-68$， $D^{\prime }\left(T_{n,2,2}^{\left(2\right)}\right)=3n^2+9n-60$，

$D^{\prime }\left(T_{n,1,4}^{\left(2\right)}\right)=3n^2+13n-56$

而 $D^{\prime }\left(R_{n-7,1,1,1}^{\left(3\right)}\right)=3n^2+5n-32$，结论成立。

基金项目

青海师范大学中青年教师科研基金资助项目(17ZR10)。