给定最大度单圈图的最小维纳指数

The Minimum Wiener Index of Unicyclic Graphs with Giving Maximum Degree

摘要: 近年来，随着结构图理论和拓扑图理论在计算机网络、图像处理等领域的应用，越来越多的图论分支理论被研究拓展，各种应用瓶颈也催生出更实际更严格的定理结论。在基站分布拓扑网络、社会关系网络等布局设计领域，代价作为衡量效率的重要指标被多方面深入研究。维纳指数是拓扑结构中最经典应用最广泛的指标之一，反应了图中任意节点对平均距离，通过降低图的维纳指数可极大减少网络布局消耗。本文定义了一类给定阶n和最大度Δ的围长为3的单圈图，并刻画了具有最小维纳指数的单圈图结构。

Abstract: In recent years, with the application of structure graph theory and topological graph theory in com-puter network, image processing and other fields, more and more branch theories of graph theory have been studied and expanded, and the bottlenecks of various application also give rise to more practical and rigorous theorem conclusions. In the field of layout design such as base station distri-bution topology network and social relationship network, cost has been in-depth studied as an important indicator to measure efficiency. Wiener index is one of the most classic and widely used indicators in topology, reflecting the average distance of any node pair in the graph, and greatly reducing the network layout consumption by reducing the Wiener index of the graph. This paper defines a class of unicyclic graphs with a girth of 3 for a given order n and the maximum degree Δ, and characterizes the structure of the unicyclic graph with the smallest Wiener index.

1. 引言

维纳指数被认为是最经典和最广泛的拓扑指数之一。维纳指数首次被用于研究化学分子图的定稿和筛选，然后对各种物理大型线进行优化，这些都可以作为图论的一部分，如通信网络、社会网络分析和运筹学，见 [1] [2] [3] [4] 。维纳索引不仅使各种给定图的边界更加清晰，而且还保持其合成指数，如超维纳索引、斯坦纳维纳索引和绕道索引。这些理论的每一个进步都为应用学科提供了新的思路和策略。经过二十多年的研究，树或其他连接图的维纳指数的边界不断收紧和表示不同的条件，如顶点的数量、边数、度序列、最大度、直径、匹配数等，在 [5] [6] [7] [8] [9] 。特别地，在 [10] 中，它通过给定的度序列确定了所有具有最大拉普拉斯谱半径的极值树， [11] 利用偶次的顶点来表征具有最小维纳指数的图的结构。

特别地，单圈图的最小维纳指数也得到了广泛的研究。例如， [12] [13] 确定了所有具有给定匹配数的单圈图中单圈图的最小维纳指数。在 [14] 中，它通过给定的周长来描述所有单圈图中具有最小和最大维纳指数的单圈图。 [15] [16] [17] 定义了所有具有n个顶点和固定直径的单圈图中的最小维纳指数。 [18] 通过给定具有垂直顶点的周长来确定单圈图的最小维纳指数。 [19] [20] 确定了在所有具有给定垂直顶点的单圈图中维纳指数最小的单圈图。

本文定义了一类给定n阶、最大度∆的单圈图，并刻画了具有最小维纳指数的单圈图结构。

2. 预备知识

2.1. 基础知识

设 $G=\left(V,E\right)$ 是一个简单无向的连通图，其中点集 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ ，边集 $E\left(G\right)=\left\{\left(u,v\right)|u,v\in V\left(G\right)\right\}$ 。图所有顶点个数称作阶数，记作n。图中顶点连接的边数称作该顶点的度，记作∆。图的圈是指从任意顶点经非重复边和顶点到起点所形成的闭合回路，圈的边数记作围长g。将有且仅有一个圈的简单连通图称作单圈图，若单圈图除去圈上所有边，则形成不多于g个以顶点为根的树，该树称作单圈图的悬挂树。维纳指数是指图中任意不重复两点距离之和，记作 $W\left(G\right)$ ，表示为

$W\left(G\right)={\displaystyle \underset{u,v\subseteq V\left(G\right)}{\sum }d}\left(u,v\right),$

其中 $d\left(u,v\right)$ 表示u与v的距离。或

$W\left(G\right)={\displaystyle \underset{e=ij\in E\left(G\right)}{\sum }{n}_e}\left(i\right)n_e\left(j\right).$

其中 $n_e\left(i\right)$ 表示与边 $e=ij$ 中顶点i相连的边数。

2.2. $\mathcal{T}\left(R,\Delta \right)$

在Fischermann [20] 中，定义一类树，记作 $\mathcal{T}\left(R,\Delta \right)$ ，其结构如图1所示，定义2.1给出图结构的定义：

定义1：(Fischermann [20] )对于 $\Delta \ge 3$ ，记 $R\in \left\{\Delta -1,\Delta \right\}$ ，令 $M_0\left(R,\Delta \right)=1$ ， $M_k\left(R,\Delta \right)=1+R+R\left(\Delta -1\right)+\cdots +R{\left(\Delta -1\right)}^{k-1}$ ，其中 $k\ge 1$ 。对于任意n，都有一些 $k\ge 0$ ，使得

$M_k\left(R,\Delta \right)\le n<M_{k+1}\left(R,\Delta \right),$

又令 $n-M_k\left(R,\Delta \right)=m\left(\Delta -1\right)+r$ ，其中 $0\le r<\Delta -1$ 。令 $\mathcal{T}\left(R,\Delta \right)$ 是一类n阶树族，其点集属于平面嵌入结构，有如下 $\mathcal{T}\left(R,\Delta \right)$ 结构：

1) 所有点都在某一 $h_i$ 层，其中 $0\le i\le k+1$ ；

2) 有且仅有一点位于 $h_0$ 层，在 $h_i$ 层有 $\min \left\{R,n-1\right\}$ 个邻居节点；

3) 位于 $h_j$ 层的任何一点都在 $h_{j-1}$ 层有且仅有一个邻居节点，在 $h_{j+1}$ 层有 $\Delta -1$ 个邻居节点，其中 $1\le j\le k-1$ ；

4) 对于位于 $h_k$ 层上最左边的 $m+1$ 个顶点， $v_1,v_2,\cdots ,v_m,v_{m+1}$ ， $v_{m+1}$ 在 $h_{k+1}$ 上有r个邻居，其他顶点在 $h_{k+1}$ 上都有 $\Delta -1$ 个邻居。

Figure 1. $\mathcal{T}\left(R,\Delta \right)$

图1. $\mathcal{T}\left(R,\Delta \right)$

2.3. $\mathcal{T}$ -子树和 $\mathcal{T}$ -单圈图

令 ${\mathcal{U}}_{\Delta }\left(n_1,n_2,\cdots ,n_g\right)$ 是一类n阶( $n=n_1+n_2+\cdots +n_g$ )，围长为g，最大度为 $\Delta$ 的单圈图，简写作 $\mathcal{U}\left(\Delta ,g,n\right)$ 。有一单圈图 $U\in \mathcal{U}\left(\Delta ,g,n\right)$ ，其单圈记作 $C_g=v_1{v}_2\cdots v_g{v}_1$ ，根节点为 $v_i$ 的悬挂树记作T，设有 $k+1$ 层，且 $\left|T_i\right|=n_i$ ，其中 $i=1,2,\cdots ,g$ 。另记该悬挂树的根节点位于 $h_0$ 层，则层数依次记作 $h_1,h_2,\cdots ,h_k$ ，令 $V_{h_i}$ 是位于 $h_i$ 层的点集，显然， $\left|V_{h_0}\right|=1$ 。该类单圈图的示例如图2所示。

Figure 2. Hanging-tree $T_i$

图2. 悬挂树 $T_i$

定义2：[ $\mathcal{T}$ -子树] 设 $U\in \mathcal{U}\left(\Delta ,g,n\right)$ ，令 $T=\left(V,E\right)$ 是单圈图中根为 $v_x$ 的悬挂树 $T_i$ 中最大的子树，该子树的根节点是 $v_i$ 的子节点。若 $T\in \mathcal{T}\left(\Delta -1,\Delta \right)$ ，那么将T记作 $T_i$ 的 $\mathcal{T}$ -子树。

若根节点为 $v_i$ 的悬挂树 $T_i$ 是由 $v_i$ 和 $\mathcal{T}$ -子树组成，那么将这类 $T_i$ 记作 $\mathcal{T}$ -悬挂树。将 $h_0,h_1,\cdots ,h_k$ 层的所有点的数量记作 $\tilde{M}\left(\Delta ,k\right)$ ，那么将得到 $T_i$ 中每层的点数最大值，如表1所示。如果 ${\left(\Delta -1\right)}^{k-1}<\left|T_i\right|<{\left(\Delta -1\right)}^k$ ，那么称 $T_i$ 是k层不饱和的。

Table 1. The maximum number of vertices each layer of T i

表1. $T_i$ 县中每层的点数最大值

定义3：[ $\mathcal{T}$ -单圈图] (Zhang [20] )单圈图 $U\in \mathcal{U}\left(\Delta ,g,n\right)$ ，若它所有悬挂树 $T_1,T_2,\cdots ,T_g$ 都是 $\mathcal{T}$ -悬挂树，则将U称为 $\mathcal{T}$ -单圈图。

3. 相关引理

本文研究围长 $g=3$ ，最大度 $\Delta \ge 4$ 的 $U,\bar{U}\in \mathcal{U}\left(\Delta ,g,n\right)$ 的维纳指数极值图结构。为方便下文解释，将其分别记作 $U\left(\Delta ,n_1,n_2,n_3\right)$ 、 $\bar{U}\left(\Delta ,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)$ ，简记作 $U,\bar{U}$ ，其 $\mathcal{T}$ -悬挂树分别记作 $T_1,T_2,T_3,{T^{\prime }}_1\text{,}{T^{\prime }}_2\text{,}{T^{\prime }}_3$ ，其中 $n_1\ge n_2\ge n_3$ ， $k_1\ge k_2\ge k_3$ ，令 $A=\Delta -1$ 。

引理1：设最大度 $\Delta \ge 4$ 的 $\mathcal{T}$ -悬挂树T是 $h_k$ 层饱和的，则其根节点v与T中所有顶点的距离和

$W\left(v,T\right)=\left(k+1\right)\times A^k-\frac{A^{k+1}-1}{A-1}.$

引理2：设最大度 $\Delta \ge 4$ 的 $\mathcal{T}$ -悬挂树T是 $h_k$ 层饱和的，则 $h_k$ 中最末顶点u与T该层中所有顶点之间的距离和为

$W\left(u,h_k\right)=4k{A}^{k-1}+\frac{2-2A^k}{A-1}.$

引理3：设最大度 $\Delta \ge 4$ 的 $\mathcal{T}$ -悬挂树T是 $h_k$ 层饱和的，则 $h_k$ 中最末顶点u与T中所有顶点之间的距离和为

$W\left(u,T\right)=\frac{\left(4k+1\right)\times A^k-A+2k}{A-1}-\frac{2A^{k+1}+4A^k-2A-4}{{\left(A-1\right)}^2}+1.$

引理4：设最大度 $\Delta \ge 4$ 的 $\mathcal{T}$ -悬挂树T是 $h_k$ 层饱和的，则T的维纳指数为

$W\left(T\right)={\displaystyle \underset{i=1}{\overset{k}{\sum }}R}\times A^{i-1}\times \left[1+W{\left(u\right)}_{T_{i-1}}+\frac{1}{2}W\left(u,h_i\right)\right],$

其中 $W{\left(u\right)}_{T_{i-1}}$ 是 $h_{i-1}$ 上u和 $h_0~h_{i-1}$ 上每个顶点之间的距离和。

4. 主要结论

$U\left(\Delta ,n_1,n_2,n_3\right)$ 到 $\bar{U}\left(V,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)$ 的四种图变换形式(如图3和图4所示)：

(a) (b)

Figure 3. Graph operation 1: $k_3$ is saturated

图3. 图转换1： $k_3$ 饱和

(a) (b)

Figure 4. Graph operation 2: $k_3$ is unsaturated

图4. 图转换2： $k_3$ 不饱和

引理5：设 $\mathcal{T}$ -单圈图 $U,\bar{U}\in \mathcal{U}\left(\Delta ,3,n\right)$ ，其中当 $\Delta =4,k_1-k_3\ge 4$ ；或当 $\Delta =5,k_1\ge 3\times k_3+6$ ，U的 $\mathcal{T}$ -悬挂树满足 $n_1=A^{k_1-1}+\left|V_{h_{k_1}}\right|,n_2=A^{k_2},n_3=A^{k_3}$ ，若 $\left|V_{h_{k_1}}\right|\le \left(A-1\right)\times A^{k_3}$ ，则将 $T_1$ 的 $h_{k_1}$ 上所有顶点移至 $T_3$ ，使其 $k_1-1$ 层饱和，得到新 $\mathcal{T}$ -单圈图 $\bar{U}$ 的 $\mathcal{T}$ -悬挂树满足 ${n^{\prime }}_1=A^{k_1-1},{n^{\prime }}_2=n_2,{n^{\prime }}_3=n_3+\left|V_{h_{k_1}}\right|$ ，则有

$h\left({T^{\prime }}_1\right)-h\left({T^{\prime }}_3\right)\le h\left(T_1\right)-h\left(T_3\right),W\left(\bar{U}\right)\le W\left(U\right).$

证明：如图3(a)所示，可知层数和点数的变化：

${k^{\prime }}_1=k_1-1,{k^{\prime }}_2=k_2,{k^{\prime }}_3=k_3+1.$

设 $\mathcal{T}$ -悬挂树 $T_1=T_1^0+V_1,{T^{\prime }}_3=T_3^0+{\bar{V}}_1$ ，其中 $T_1^0$ 是 $k_1-1$ 层饱和的， $T_3^0$ 是 $k_3$ 层饱和的， $\left|V_1\right|=\left|V_{h_{k_1}}\right|$ 。考虑

到图转换的结果变化，可知 $\Delta W=W\left(U\right)-W\left(\bar{U}\right)={\displaystyle \underset{x\subseteq U}{\sum }d}\left(V_1,x\right)-{\displaystyle \underset{y\subseteq \bar{U}}{\sum }d}\left({\bar{V}}_1,y\right)$ ，分为以下四步：

1) $W\left(V_1,T_2\cup {T^{\prime }}_2\right)$ 和 $W\left({\bar{V}}_1,T_2\cup {T^{\prime }}_2\right)$ 。

$\begin{array}{c}{W}_1=W\left(V_1,T_2\cup {T^{\prime }}_2\right)-W\left({\bar{V}}_1,T_2\cup {T^{\prime }}_2\right)\\ =\left|V_1\right|\times \left(k_1-k_3-1\right)\cdot n_2.\end{array}$

2) $W\left(V_1,T_1^0\right)$ 和 $W\left({\bar{V}}_1,T_3^0\right)$ 。

$\begin{array}{l}W\left(V_1,T_1^0\right)=\left|V_1\right|\times \left(W\left(u,T_1^0\right)+\left|T_1^0\right|\right),\\ W\left({\bar{V}}_1,T_3^0\right)={\bar{V}}_1\times \left(W\left(u,T_3^0\right)+T_3^0\right).\end{array}$

3) $W\left(V_1,T_3\right)$ 和 $W\left({\bar{V}}_1,T_1^0\right)$ 。

$\begin{array}{l}W\left(V_1,T_3\right)=W\left(V_1,T_3^0\right)=\left|V_1\right|\times \left(W\left(v,T_3^0\right)+\left(k_1+1\right)\times \left|T_3^0\right|\right),\\ W\left({\bar{V}}_1,T_1^0\right)=\left|{\bar{V}}_1\right|\times \left[W\left({\bar{V}}_1,T_1^0\right)+\left(k_3+2\right)\times \left|T_1^0\right|\right].\end{array}$

4) $W\left(V_1\right)$ 和 $W\left({\bar{V}}_1\right)$ 。

二者在图中的结构相同，因此其差值为0。

已知 $\left|T_1^0\right|=A^{k_1-1},\left|T_3\right|=\left|T_3^0\right|=A^{k_3},\left|V_1\right|={\bar{V}}_1$ ，由引理1、2、3和4可得：

$\begin{array}{l}W\left(U\right)-W\left(\bar{U}\right)\\ =W\left(V_1,T_1^0\right)+W\left(V_1,T_2\right)+W\left(V_1,T_3\right)+W\left(V_1\right)\\ -W\left({\bar{V}}_1,T_1^0\right)-W\left({\bar{V}}_1,T_2\right)-W\left({\bar{V}}_1,T_3^0\right)-W\left({\bar{V}}_1\right)\\ \ge \left|V_1\right|\times \{\left[\frac{5-A}{A-1}\times k_1-k_3-\frac{4A+2}{{\left(A-1\right)}^2}\right]\times A^{k_1-1}+\left[k_1-\frac{5-A}{A-1}\times k_3+\frac{A^2-2A+7}{{\left(A-1\right)}^2}\right]\times A^{k_3}\\ +\left(k_1-k_3\right)\times \left(n_2+\frac{2}{A-1}\right)\}.\end{array}$

当 $A=3$ ，即 $\Delta =4$ ，可得

$\begin{array}{l}W\left(U\left(4,n_1,n_2,n_3\right)\right)-W\left(\bar{U}\left(4,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\right)\\ =\left|V_1\right|\times \left\{\left(k_1-k_3-\frac{7}{2}\right)\times 3^{k_1-1}+\left(k_1-k_3+\frac{7}{2}\right)\times 3^{k_3}+\left(k_1-k_3\right)\times \left(n_2+1\right)\right\}.\end{array}$

设 $k_1-k_3\ge 4$ ，则各个单项式系数都为正，则有 $W\left(U\left(4,n_1,n_2,n_3\right)\right)\ge W\left(\bar{U}\left(4,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\right)$ 。

当 $A=4$ ，即 $\Delta =5$ ，可得

$\begin{array}{l}W\left(U\left(5,n_1,n_2,n_3\right)\right)-W\left(\bar{U}\left(5,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\right)\\ =\left|V_1\right|\times \left\{\left(\frac{1}{3}\times k_1-k_3-2\right)\times 4^{k_1-1}+\left(k_1-\frac{1}{3}\times k_3+\frac{5}{3}\right)\times 4^{k_3}+\left(k_1-k_3\right)\times \left(n_2+\frac{2}{3}\right)\right\}.\end{array}$

设 $k_1-k_3\ge 4$ ，则各个单项式系数都为正，则有 $W\left(U\left(5,n_1,n_2,n_3\right)\right)\ge W\left(\bar{U}\left(5,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\right)$ 。

□

引理6：设 $\mathcal{T}$ -单圈图 $U,\bar{U}\in \mathcal{U}\left(\Delta ,3,n\right)$ ，其中当 $\Delta =4,k_1-k_3\ge 4$ ；或当 $\Delta =5,k_1\ge 3\times k_3+6$ ，U的 $\mathcal{T}$ -悬挂树满足 $n_1=A^{k_1-1}+\left|V_{h_{k_1}}\right|,n_2=A^{k_2},n_3=A^{k_3}$ ，若 $\left(A-1\right)\times A^{k_3}<\left|V_{h_{k_1}}\right|\le \left(A-1\right)\times A^{k_1-1}$ ，则将 $T_1$ 的 $h_{k_1}$ 上 $\left(A-1\right)\times A^{k_3}$ 个顶点移至 $T_3$ ，使其 $k_3+1$ 层饱和，得到新 $\mathcal{T}$ -单圈图 $\bar{U}$ 的 $\mathcal{T}$ -悬挂树满足 ${n^{\prime }}_1=n_1-\left(A-1\right)\times A^{k_3},{n^{\prime }}_2=n_2,{n^{\prime }}_3=A^{k_3+1}$ ，则有

$h\left({T^{\prime }}_1\right)-h\left({T^{\prime }}_3\right)\le h\left(T_1\right)-h\left(T_3\right),W\left(\bar{U}\right)\le W\left(U\right).$

证明：如图3(b)所示，可知层数和点数的变化：

${k^{\prime }}_1=k_1,{k^{\prime }}_2=k_2,{k^{\prime }}_3=k_3+1.$

设 $\mathcal{T}$ -悬挂树 $T_1=T_1^0+V_1+V_2,{T^{\prime }}_3=T_3^0+{\bar{V}}_1$ ，其中 $T_1^0$ 是 $k_1-1$ 层饱和的， $T_3^0$ 是 $k_3$ 层饱和的，

$\left|V_1\right|=\left(A-1\right)\times A^{k_3}$ 。考虑到图转换的结果变化，可知 $\Delta W=W\left(U\right)-W\left(\bar{U}\right)={\displaystyle \underset{x\subseteq U}{\sum }d}\left(V_1,x\right)-{\displaystyle \underset{y\subseteq \bar{U}}{\sum }d}\left({\bar{V}}_1,y\right)$ ，分为

以下五步，前四步与引理5的证明类似，第五步为 $W\left(V_1,V_2\right)$ 与 $W\left({\bar{V}}_1,V_2\right)$ 的差，分为两种情况。

情况1： $T_1$ 是 $k_1$ 饱和的。

$\begin{array}{c}\left|V_2\right|=A^{k_3}+\left(A-1\right)\times A^{k_3+1}+\left(A-1\right)\times A^{k_3+2}+\cdots +\left(A-1\right)\times A^{k_1-1}+A^{k_1}\\ =\left(A-1\right)\times A^{k_1}-\left(A-1\right)\times A^{k_3},\end{array}$

$\begin{array}{c}W\left(V_1,V_2\right)=\left|V_1\right|\times [\left(A-1\right)\times \left(k_3+1\right)\times A^{k_3}+\left(A-1\right)\times \left(k_3+2\right)\times 2\times A^{k_3+1}\\ +\left(A-1\right)\times \left(k_3+3\right)\times 2\times A^{k_3+2}+\cdots +\left(A-1\right)\times k_1\times 2\times A^{k_1-1}\\ +\left(A-1\right)\times \left(k_1+1\right)\times A^{k_1}],\end{array}$

$W\left(V_1,V_2\right)={\left|V\right|}_1\times 2\left(A-1\right)\times \left\{A^{k_1}\times \left[1+\frac{A\times k_1}{A-1}-\frac{A}{{\left(A-1\right)}^2}\right]-A^{k_3}\times \left[1+\frac{k_3}{A-1}-\frac{A}{{\left(A-1\right)}^2}\right]\right\}.$

$\begin{array}{l}W\left(V_1,V_2\right)-W\left({\bar{V}}_1,V_2\right)\\ =\left|V_1\right|\times \left(A-1\right)\times \left\{\left[\frac{A+1}{A-1}\times k_1-k_3-\frac{A^2+1}{A-1}\right]\times A^{k_1}+\left[k_1-\frac{A-3}{A-1}\times k_3+\frac{A^2+1}{{\left(A-1\right)}^2}\right]\times A^{k_3}\right\}\\ >0.\end{array}$

前四部分的距离差之和与第五部分均大于零，结论成立。

情况2： $T_1$ 是 $k_1$ 不饱和的。

2-1：

$\begin{array}{c}\left|V_2\right|=A^{k_3}+\left(A-1\right)\times A^{k_3+1}+\left(A-1\right)\times A^{k_3+2}+\cdots +\left(A-1\right)\times A^{k_1-1}+m\\ =A^{k_1}-\left(A-1\right)\times A^{k_3}+m,\end{array}$

$W\left(V_1,V_2\right)=\left|{\bar{V}}_1\right|\times \left[2\times \left(k_1-\frac{A^2-4A+6}{A-1}\right)\times A^{k_1}-\left(2A-2+2k_3-\frac{2A}{A-1}\right)\times A^{k_3}+2\left(k_1+1\right)\times m\right],$

$W\left({\bar{V}}_1,V_2\right)=\left|{\bar{V}}_1\right|\times \left(k_1+k_3+3\right)\times \left[A^{k_1}-\left(A-1\right)\times A^{k_3}+m\right],$

$\begin{array}{l}W\left(V_1,V_2\right)-W\left({\bar{V}}_1,V_2\right)\\ =\left|V_1\right|\times \left\{\left(k_1-\frac{2A^2-A+1}{A-1}\right)\times A^{k_1}+\left[\left(A-1\right)\times k_1+\left(A-1\right)\times k_3+\frac{A^2+1}{A-1}\right]\times A^{k_3}-\left(k_1+k_3+3\right)\times m\right\}.\end{array}$

其中 $1\le m\le A^{k_1}$ 。

当 $A=3$ ，即 $\Delta =4$ ，设 $k_1-k_3-3\ge 0,k_2\ge k_3$ ，得到五部分之和大于零，显然，当 $k_1\ge k_3+4$ 时，结论成立。

当 $A=4$ ，即 $\Delta =5$ ，设 $k_1\ge \frac{3}{5}\times k_3+\frac{9}{5},k_2\ge k_3$ ，得到五部分之和大于零，显然，当 $k_1\ge 3\times k_3+6$ 时，结论成立。

2-2：

$\begin{array}{c}\left|V_2\right|=A^{k_3}+\left(A-1\right)\times A^{k_3+1}+\left(A-1\right)\times A^{k_3+2}+\cdots +\left(A-1\right)\times A^t+n\\ =A^{t+1}-\left(A-1\right)\times A^{k_3}+m,\end{array}$

$\begin{array}{c}W\left(V_1,V_2\right)=\left|V_1\right|\times \frac{4}{A-1}\times \{\left(3A+2A\times k_3-A^2-A^2\times k_3+1\right)\times A^{k_3}\\ +\left[A\times \left(t-1\right)-\left(t+2\right)\right]\times A^{t+1}+\left(A-1\right)\times \left(t+2\right)\times m\}\end{array}$

$W\left({\bar{V}}_1,V_2\right)=\left|V_1\right|\times \left(k_1+k_3+3\right)\times \left[A^{t+1}-\left(A-1\right)\times A^{k_3}+n\right],$

$\begin{array}{l}W\left(V_1,V_2\right)-W\left({\bar{V}}_1,V_2\right)\\ =\left|V_1\right|\times [\left(4t-k_1-k_3+\frac{A-5}{A-1}\right)\times A^{t+1}+\left[\left(A-1\right)\times k_1+\left(\frac{4}{A-1}-3\times A+3\right)\times k_3-7-A\right]\times A^{k_3}\\ \stackrel{}{}+\left(4t-k_1-k_3+1\right)\times m],\end{array}$

其中 $k_3+1\le t\le k_1-2$ ， $0<m<\left(A-1\right)\times A^{t+1}$ 。

当 $A=3$ ，即 $\Delta =4$ ，设 $k_1-k_3\ge 4$ ， $k_2\ge k_3$ ，五部分距离差相加，由引理1、2、3和4得

$\begin{array}{l}W\left(U\right)-W\left(\bar{U}\right)\\ =\left|V_1\right|\times \{\left(k_1-k_3-\frac{7}{2}\right)\times 3^{k_1-1}+\left(k_1-k_3\right)\times \left(3^{k_2}+1\right)+\left(3k_1-5k_3-\frac{15}{2}\right)\times 3^{k_3}\\ \stackrel{}{}+\left(4t-k_1-k_3-2\right)\times 3^{t+1}+\left(4t-k_1-k_3+11\right)\times m\}\\ >\left|V_1\right|\times \left\{\left(k_1-k_3-\frac{7}{2}\right)\times 3^{k_1-1}+\left(4t+3k_1-3k_3-\frac{19}{2}\right)\times 3^{k_3}+\left(4t-k_1-k_3+11\right)\times n+\left(k_1-k_3\right)\right\}\\ >0.\end{array}$

当 $A=4$ ，即 $\Delta =5$ ，可得五部分距离差相加，由引理1、2、3和4得

$\begin{array}{l}4t-k_1-k_3-\frac{1}{3}\ge 0,\\ 3k_1-\frac{23}{5}\times k_3-11\ge 0,\\ 3\times k_3-k_1+5\ge 0.\end{array}$

因此，当 $A=4$ ，即 $\Delta =5$ ， $k_1\ge 3\times k_3+6$ ，可得 $W\left(\bar{U}\right)\le W\left(U\right)$ 。

□

引理7：设 $\mathcal{T}$ -单圈图 $U,\bar{U}\in \mathcal{U}\left(\Delta ,3,n\right)$ ，其中当 $\Delta =4,k_1-k_3\ge 4$ ；或当 $\Delta =5,k_1\ge 3\times k_3+6$ ，U的 $\mathcal{T}$ -悬挂树满足 $n_1=A^{k_1-1}+\left|V_{h_{k_1}}\right|,n_2=A^{k_2},n_3=A^{k_3-1}+\left|V_{h_{h_3}}\right|$ ，若 $1\le \left|V_{h_{k_3}}\right|<\left(A-1\right)\times A^{k_3-1}$ ， $1\le \left|V_{h_{k_1}}\right|\le \left(A-1\right)\times A^{k_3-1}-\left|V_{h_{k_3}}\right|$ ，则将 $T_1$ 的 $h_{k_1}$ 上所有顶点移至 $T_3$ 的 $k_3$ 层，使得 $T_1$ 的 $k_1-1$ 层饱和，得到新 $\mathcal{T}$ -单圈图 $\bar{U}$ 的 $\mathcal{T}$ -悬挂树满足 ${n^{\prime }}_1=A^{k_1-1},{n^{\prime }}_2=n_2,{n^{\prime }}_3=n_3+\left|V_{h_{k_1}}\right|$ ，则有

$h\left({T^{\prime }}_1\right)-h\left({T^{\prime }}_3\right)\le h\left(T_1\right)-h\left(T_3\right),W\left(\bar{U}\right)\le W\left(U\right).$

证明：如图4(a)所示，可知层数和点数的变化：

${k^{\prime }}_1=k_1-1,{k^{\prime }}_2=k_2,{k^{\prime }}_3=k_3.$

设 $\mathcal{T}$ -悬挂树 $T_1=T_1^0+V_1,{T^{\prime }}_3=T_3^0+V_3+{\bar{V}}_1$ ，其中 $T_1^0$ 是 $k_1-1$ 层饱和的， $T_3^0$ 是 $k_3$ 层饱和的， $\left|V_1\right|=\left|V_{h_{k_1}}\right|$ ， $V_3$ 是原 $T_3$ 中 $h_{k_3}$ 上的顶点集。考虑到图转换的结果变化，可知 $\Delta W=W\left(U\right)-W\left(\bar{U}\right)={\displaystyle \underset{x\subseteq U}{\sum }d}\left(V_1,x\right)-{\displaystyle \underset{y\subseteq \bar{U}}{\sum }d}\left({\bar{V}}_1,y\right)$ ，分为以下五步，前四步与引理5的证明类似，第五步为 $W\left(V_1,V_3\right)$ 与 $W\left({\bar{V}}_1,V_3\right)$ 的差， $W\left(V_1,V_3\right)-W\left({\bar{V}}_1,V_3\right)\ge \left|V_1\right|\times \left|V_3\right|\times \left(k_1+1+k_3-2k_3\right)>0$ 。

五部分距离差均为非负，结论成立。

□

引理8：设 $\mathcal{T}$ -单圈图 $U,\bar{U}\in \mathcal{U}\left(\Delta ,3,n\right)$ ，其中当 $\Delta =4,k_1-k_3\ge 4$ ；或当 $\Delta =5,k_1\ge 3\times k_3+6$ ，U的 $\mathcal{T}$ -悬挂树满足 $n_1=A^{k_1-1}+\left|V_{h_{k_1}}\right|,n_2=A^{k_2},n_3=A^{k_3-1}+\left|V_{h_{h_3}}\right|$ ，若 $1\le \left|V_{h_{k_3}}\right|<\left(A-1\right)\times A^{k_3-1}$ ，，则将 $T_1$ 的 $h_{k_1}$ 上部分顶点移至 $T_3$ 的 $k_3$ 层，使其 $k_1-1$ 层饱和，得到新 $\mathcal{T}$ -单圈图 $\bar{U}$ 的 $\mathcal{T}$ -悬挂树满足 ${n^{\prime }}_1=A^{k_1-1},{n^{\prime }}_2=n_2,{n^{\prime }}_3=n_3+\left|V_{h_{k_1}}\right|$ ，则有

$h\left({T^{\prime }}_1\right)-h\left({T^{\prime }}_3\right)\le h\left(T_1\right)-h\left(T_3\right),W\left(\bar{U}\right)\le W\left(U\right).$

证明：如图4(b)所示，可知层数和点数的变化：

${k^{\prime }}_1=k_1,{k^{\prime }}_2=k_2,{k^{\prime }}_3=k_3.$

设 $\mathcal{T}$ -悬挂树 $T_1=T_1^0+V_1+V_2,{T^{\prime }}_3=T_3^0+V_3+{\bar{V}}_1$ ，其中 $T_1^0$ 是 $k_1-1$ 层饱和的， $T_3^0$ 是 $k_3$ 层饱和的， $\left|V_1\right|=\left|V_{h_{k_1}}\right|$ ， $V_2$ 、 $V_3$ 分别是原悬挂树中 $h_{k_1}$ 、 $h_{k_3}$ 上的顶点集。考虑到图转换的结果变化，可知

$\Delta W=W\left(U\right)-W\left(\bar{U}\right)={\displaystyle \underset{x\subseteq U}{\sum }d}\left(V_1,x\right)-{\displaystyle \underset{y\subseteq \bar{U}}{\sum }d}\left({\bar{V}}_1,y\right)$ ，分为以下五步，前四步与引理5证明类似，第五步为 $W\left(V_1,V_3\right)+W\left(V_1,V_2\right)$ 与 $W\left({\bar{V}}_1,V_2\right)+W\left({\bar{V}}_1,V_3\right)$ 的差。

考虑到 $V_1,V_2,V_3,\overline{V_1}$ 在 $\mathcal{T}$ -悬挂树中顶点分布，将 $V_2$ 划分为两部分，其中一部分与 $V_3$ 相等，便可得 $\left(V_1,V_3\right)=W\left({\bar{V}}_1,V_2\right),W\left(V_1,V_2\right)=W\left({\bar{V}}_1,V_3\right)$ 。

五部分距离差均为非负，结论成立。

□

定理1：设 $\mathcal{T}$ -单圈图 $U\left(\Delta ,n_1,n_2,n_3\right),\bar{U}\left(\Delta ,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\in \mathcal{U}\left(\Delta ,3,n\right)$ ，其中当 $\Delta =4,k_1-k_3\ge 4$ ；或当 $\Delta =5,k_1\ge 3\times k_3+6$ ，有 $\mathcal{T}$ -悬挂树 $\bar{U}\left(\Delta ,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)$ 满足

$W\left(\bar{U}\left(\Delta ,{n^{\prime }}_1,{n^{\prime }}_2,{n^{\prime }}_3\right)\right)\le W\left(U\left(\Delta ,n_1,n_2,n_3\right)\right).$

证明： $\mathcal{T}$ -单圈图U有四类图转换，如图3和图4所示，分别对应引理1、2、3和4。

任一 $\mathcal{T}$ -单圈图U，当 $\Delta =4$ 且 $k_1\ge k_3+4$ ；或当 $\Delta =5$ 且 $k_1\ge 3\times k_3+6$ ，通过不断调整顶点分布，使得 $\mathcal{T}$ -悬挂树间层差降低，最终有 $k_1\ge k_2\ge k_3$ ， $k_1\ge k_3+4$ 或 $k_1\ge 3\times k_3+6$ 。

□

5. 总结展望

以上述单圈图定理为基础，使用末层划分的图转换方法，将转换过程按图结构分为四种情况，以层差关系刻画两类单圈图极值图结构，同时更正了前人结论。

本文研究了关于单圈图的维纳指数极图结构，经过计算方式的探索与比较以及图结构分析，取得一定成果，但是本文研究方向仍有值得探索的问题：

1) 给定阶数、最大度和围长的单圈图，寻求合适的方法，找到与 $\Delta$ 相关的函数 $n\ge f\left(\Delta \right)$ 限定，得到维纳指数最小时的极图结构特点。

2) 将理论结果与实验数据相结合，探索维纳指数极值图结构中层差、最大度、阶数，甚至是围长的关系。

3) 将图论思想与模型结合，用理学思想运用计算机技术，学会用计算机技术便捷、有预见性地解决图论极值与极图问题。

基金项目

国家自然科学基金项目(12201273)；浙江省自然科学基金项目(LY21A010002)。