给定直径和阶的具有最大Wiener指标的单圈图 The Maximal Wiener Index of UnicyclicGraph with Given Diameter and Order

doi:10.12677/AAM.2020.93038

Advances in Applied Mathematics
Vol. 09 No. 03 ( 2020 ), Article ID: 34537 , 12 pages
10.12677/AAM.2020.93038

The Maximal Wiener Index of Unicyclic Graph with Given Diameter and Order

Huimin Wang, Yuanpei Wang, Chenchen Cao, Qiang Sun^*

●How to Cite this Article

School of Mathematical Science, Yangzhou University, Yangzhou Jiangsu

Received: Feb. 25^th, 2020; accepted: Mar. 9^th, 2020; published: Mar. 16^th, 2020

ABSTRACT

The Wiener index of a graph is one of the most very well-researched topological indices, i.e. graph theoretic invariants of molecular graphs. Some interesting questions remain largely unsolved despite being easy to state and comprehend. In this paper, we investigate a conjecture proposed by DelaVina and Waller [1], namely, the graphs of order 2d + 1 and diameter d have Wiener index less or equal than the cycle of order 2d + 1. In this paper, we proved that this conjecture is true for unicyclic graphs with vertices outside of the cycle not too many.

Keywords:Wiener Index, Unicyclic Graph, Maximum

给定直径和阶的具有最大Wiener指标的单圈图

王惠敏，王元培，曹陈琛，孙强^*

扬州大学数学科学学院，江苏扬州

收稿日期：2020年2月25日；录用日期：2020年3月9日；发布日期：2020年3月16日

摘要

图的Wiener指标是图论中研究的比较深刻的拓扑指标之一，结果很丰富，同时也有许多有趣的问题没有被解决，尽管这些问题很容易表述也很容易被理解。在这篇文章中，我们着重研究由DelaVina和Waller [1] 提出的一个猜想，即：点数是2d + 1，直径为d的图的Wiener指标都不超过点数是2d + 1的圈的。本文证明了该猜想对于单圈且圈外顶点数不多的图是正确的。

关键词 :Wiener指标，单圈图，最大值

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 研究背景

1.1. 研究历史

令 $G = (V, E)$ 是一个简单的连通图。图G的Wiener指标是指图G中所有点对的距离和，即

$W (G) = \sum_{{u, v} \subseteq V (G)} d_{G} (u, v),$

其中 $d_{G} (u, v)$ 表示 $u, v$ 之间的距离。

Wiener指标是由Harold Wiener [2] 最先发现的，用以研究烷烃沸点的一种分子拓扑指标，它是指无环烷烃图中碳原子对之间键的数量的集合。1971年，Hosoya证明了Wiener指标等于分子图中的直径矩阵的元素总和的一半，由此，Wiener指标的定义被延伸到了有圈图中。

在近些年中，Wiener指标的最大与最小问题吸引了许多学者的研究，并有了一定的发现。Entringer，Jackson和Snyder [3] 在1976年用到了 $W (G)$ 的定义。随着有关于Wiener指标的深入，更多的结果被发现 [4] [5]。在所有阶为n的图中，路具有最大Wiener指标，星图具有最小Wiener指标。有关于给定条件下图的Wiener指标极值问题有许多，如：周波教授 [6] 研究了给定点数与匹配数的图的最小Wiener指标。于桂海教授 [7] 刻画了给定周长的具有极大与极小Wiener指标的图。在这些问题中，由DelaVina和Waller [1] 提出的猜想极大地促进了Wiener指标的研究：

猜想1：阶为 $2 d + 1$ ，直径为 $d > 2$ 的连通图G中，具有最大Wiener指标的图是圈。

为了研究这个猜想，我们将问题范围从连通图缩小到单圈图。在本文中，我们将研究给定直径和阶的具有最大Wiener指标的单圈图。我们将证明以下定理：

定理1：在阶为 $2 d + 1$ ，直径为d，圈的阶为 $2 d + 1 - k$ 的单圈图G中，如果 $d > \frac{{(k + 1)}^{2}}{4}$ ，则 $W (G) \leq W (C)$ ，圈 $C = u_{0} u_{1} u_{2} \dots u_{2 d} u_{0}$ 。

1.2. 术语介绍

我们简单介绍一下本文会用到的符号，对未说明的符号请参考文献 [5]。在本文中，我们主要研究简单的无向图 $G = (V, E)$ ， $V, E$ 分别表示图的点集和边集。 $d_{G} (u, v)$ 表示点 $u, v$ 之间的距离，即连接 $u, v$ 两点的最短路的长度。连接点u的边数称为u的度，度为1的点称为悬挂点。路是由无重复的顶点和边构成的序列 $v_{0}, e_{1}, v_{1}, \dots, e_{k}, v_{k}$ ，对于 $1 \leq i \leq k$ ，边 $e_{i}$ 的顶点为 $v_{i - 1}$ 和 $v_{i}$ 。如果路的顶点 $v_{0} = v_{k}$ ，则它构成圈。连通的无圈图称为树，只有一个圈的图称为单圈图。

我们定义 $G = C_{u_{0} u_{1} u_{2} \dots u_{2 d - k}} (T_{0} T_{1} T_{2} \dots T_{2 d - k})$ 是阶为 $2 d + 1$ 的单圈图，它有着阶为 $2 d + 1 - k$ 的圈 $C (2 d + 1 - k) = u_{0} u_{1} u_{2} \dots u_{2 d - k} u_{0}$ 与链接在圈上的树 $T_{0}, T_{1}, \dots, T_{2 d - k}$ 。当 $T_{i}$ 的阶为0时， $T_{i}$ 不存在。

为了方便证明中的叙述，下面我们介绍几个特殊的定义：

1.2.1. 定义1

令 $B (n_{i}, l_{i})$ 是阶为 $n_{i}$ ，直径为 $l_{i} - 1$ 的扫帚树，其图形是阶为 $n_{i} - l_{i} + 3$ 的星状树，其中一条边被分割成 $l_{i} - 2$ 条边的路。如图1所示，我们将路上的顶点标为 $v_{i, 1}, v_{i, 2}, \dots, v_{i, l_{i} - 1}$ ，并且顶点 $v_{i, l_{i} - 1}$ 是度为 $n_{i} - l_{i} + 1$ 的点。令其他与顶点 $v_{i, l_{i} - 1}$ 相连的悬挂点按逆时针标为 $v_{i, l_{i}}, v_{i, l_{i} + 1}, \dots, v_{i, n_{i}}$ 。

Figure 1. Definition 1- $B (n_{i}, l_{i})$

图1. 定义1- $B (n_{i}, l_{i})$

1.2.2. 定义2

令图H是图G的子图。 $x_{1} x_{2}$ 是图H的边， $x_{1} x_{3}$ 是图 $G - H$ 的边，则图 $H - x_{1} x_{2} + x_{1} x_{3}$ 定义为由图删去边 $x_{1} x_{2}$ 并加上边 $x_{1} x_{3}$ 的图。

1.2.3. 定义3

在图 $G = (V, E)$ 中，令 $H_{1}$ 和 $H_{2}$ 是图G的子图，图 ${H^{'}}_{1}$ 和 ${H^{'}}_{2}$ 分别由图 $H_{1}$ 和 $H_{2}$ 变化而来，则有 $G^{'} = G - H_{1} - H_{2} + {H^{'}}_{1} + {H^{'}}_{2}$ ， $ω_{G} (H_{1}, H_{2}) = \sum_{v_{i} \in H_{1}, v_{j} \in H_{2}} d (v_{i}, v_{j})$ 和 $Δ W_{G G^{'}} (H_{1}, H_{2}) = ω_{G^{'}} ({H^{'}}_{1}, {H^{'}}_{2}) - ω_{G} (H_{1}, H_{2})$ 。

1.2.4. 定义4

令 $G = C_{u_{0} u_{1} u_{2} \dots u_{2 d - k}} (T_{0} T_{1} T_{2} \dots T_{2 d - k})$ ，定义 $G_{d, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k}))$ 是 $T_{0}, T_{1}, \dots, T_{2 d - k}$ 均为扫帚树 $B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k})$ ，且 $B (n_{j}, l_{j})$ 与圈C之间以边 $v_{j, 1} u_{j} (0 \leq j \leq 2 d - k)$ 相连的图G，其中d为图的直径， $2 d + 1$ 为图的阶，i为图中所有阶不为0的扫帚树的总数。

1.2.5. 定义5

在图 $G = G_{d, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k}))$ 中，若扫帚树 $B (n_{i}, l_{i})$ 和 $B (n_{j}, l_{j}) (i \neq j)$ 满足 $l_{i} + l_{j} + d_{G} (u_{i}, u_{j}) = d$ ，则令 $P (i, j) = {B (n_{i}, l_{i}), B (n_{j}, l_{j})}$ 。

2. 引理和结论

为了证明定理1，我们首先引入几个引理。

2.1. 引理1

扫帚树 $B (n_{i}, l_{i})$ 的Wiener指标为：

$W (B (n_{i}, l_{i})) = \sum_{j = 1}^{l_{i} - 1} j (l_{i} - j - 1) + 2 C_{n_{i} - l_{i} + 1}^{2} + (n_{i} - l_{i} + 1) \sum_{i = 1}^{l_{i} - 1} j$

2.2. 引理2

令图G为一个阶为 $2 d + 1$ ，直径为d的单圈图，圈C是图G的一个阶为 $2 d + 1 - k$ 的子图。如图2，令 $v_{1}$ 为图 $G - C$ 的一个度大于等于3的顶点，同时与 $v_{2}$ 和 $v_{3}$ 相连，且有 $v_{2}$ 和 $v_{3}$ 到圈C的直径是 $v_{1}$ 到圈C的直径加1，即 $d (C, v_{2}) = d (C, v_{3}) = d (C, v_{1}) + 1$ 。保证图G的直径不变，将图G变化为图 $G^{'} = G - v_{1} v_{2} + v_{2} v_{3}$ 。当 $d > k$ 时，有 $W (G^{'}) \geq W (G)$ 。

Figure 2. Lemma 1

图2. 引理1

证明：图 $G_{1}, G_{2}, G_{3}$ 都是图G删去边 $v_{1} v_{2}$ 和 $v_{1} v_{3}$ 得到的部分，其中 $v_{1} \in G_{1}, v_{2} \in G_{2}, v_{3} \in G_{3}$ 并且 $C \in G_{1}$ 。保证图G的直径不变，令 $G^{'} = G - v_{1} v_{2} + v_{2} v_{3}$ ，则有 $Δ W = W (G^{'}) - W (G) = n (G_{2}) [n (G_{1}) - n (G_{3})]$ 。

当 $d > k$ 时，有，则 $Δ W > 0$ ，即 $W (G^{'}) \geq W (G)$ 。

2.3. 引理3

令图G为一个阶为 $2 d + 1$ ，直径为d的单圈图，圈C是图G的一个阶为 $2 d + 1 - k$ 的子图。如图3， $H_{0}$ 是图 $G - C$ 的子图，且扫帚树 $B (n_{i}, l_{i}), B (n_{j}, l_{j})$ 是图G的子图且链接于同一个顶点v。 $l_{i} = l_{j}$ ， $n_{i} - n_{j} > 0$ 且 $v \notin B (n_{i}, l_{i})$ ， $v \notin B (n_{j}, l_{j})$ 。令 $G^{'} = G - B (n_{i}, l_{i}) - B (n_{j}, l_{j}) + B (n_{i} - 1, l_{i}) + B (n_{j} + 1, l_{j})$ ，当 $d > k$ 时，有 $W (G^{'}) \geq W (G)$ 。

Figure 3. Lemma3

图3. 引理3

证明：由条件可知： $Δ W = W (G^{'}) - W (G) = (2 l_{i} - 2) (n_{i} - 1 - n_{j})$ 。

明显当 $n_{i} - n_{j} > 0$ 时， $Δ W \geq 0$ ，即 $W (G^{'}) \geq W (G)$ 。

2.4. 引理4

令图G为一个阶为 $2 d + 1$ ，直径为d的单圈图，圈C是图G的一个阶为 $2 d + 1 - k$ 的子图。如图4， $H_{0}$ 是图 $G - C$ 的子图，且扫帚树 $B (n_{i}, l_{i}), B (n_{j}, l_{j})$ 是图G的子图且链接于同一个顶点v。 $l_{i} = l_{j}$ ， $n_{i} - n_{j} = 0$ 或1，且 $v \notin B (n_{i}, l_{i}), B (n_{j}, l_{j})$ 。令 $G^{'} = G - B (n_{i}, l_{i}) - B (n_{j}, l_{j}) + B (n_{i} + n_{j}, l_{i})$ ，当 $d > \frac{{(k + 1)}^{2}}{4}$ 时，有 $W (G^{'}) > W (G)$ 。

Figure 4. Lemma 4

图4. 引理4

证明：令

$\begin{matrix} Δ W = W (G^{'}) - W (G) \\ = [W (C^{'}) + ω_{G} (B (n_{i} + n_{j}, l_{i})) + ω_{G} (B (n_{i} + n_{j}, l_{i}), C^{'})] \\ - [W (C^{'}) + W (B (n_{i}, l_{i})) + W (B (n_{j}, l_{j})) + ω_{G} (B (n_{i}, l_{i}), B (n_{j}, l_{j})) \\ + ω_{G} (B (n_{i}, l_{i}), C^{'}) + ω_{G} (B (n_{j}, l_{j}), C^{'})] \end{matrix}$

$\begin{array}{l} = [W (C^{'}) + ω_{G} (B (n_{i} + n_{j}, l_{i})) + ω_{G} (B (n_{i} + n_{j}, l_{i}), C^{'})] \\ - [W (C^{'}) + W (B (n_{i}, l_{i})) + W (B (n_{j}, l_{j})) + ω_{G} (B (n_{i}, l_{i}), B (n_{j}, l_{j})) \\ + ω_{G} (B (n_{i}, l_{i}), C^{'}) + ω_{G} (B (n_{j}, l_{j}), C^{'})] \end{array}$

$\begin{array}{l} = [W (B (n_{i} + n_{j}, l_{i})) - W (B (n_{i}, l_{i})) - W (B (n_{j}, l_{j})) - ω_{G} (B (n_{i}, l_{i}), B (n_{j}, l_{j}))] \\ + [ω_{G} (B (n_{i} + n_{j}, l_{i}), C^{'}) - ω_{G} (B (n_{i}, l_{i}), C^{'}) - ω_{G} (B (n_{j}, l_{j}), C^{'})] \\ = [W (B (n_{i} + n_{j}, l_{i})) - W (B (n_{i}, l_{i})) - W (B (n_{j}, l_{j})) - (n_{i} ω_{j} + n_{j} ω_{i})] \\ + n (C^{'}) \sum_{k = 1}^{l_{i} - 1} k \end{array}$

其中 $ω_{i} = d_{B (n_{i}, l_{i})} (v) = \sum_{k = 1}^{l_{i}} k + l_{i} (n_{i} - l_{i})$ 。

当 $l_{i} = l_{j} = l$ ， $n_{i} = n_{j} = n$ 时， $2 n + n (C^{'}) = 2 d + 1$ ，则有 $Δ W = \frac{1}{3} (l - 1) (3 d l + l^{2} - 2 l - 6 n^{2}) > \frac{1}{3} (6 d - 6 n^{2}) > 2 \times \frac{{(k + 1)}^{2}}{4} - 2 \times {(\frac{k}{2})}^{2} = k + \frac{1}{2} > 0$ 。所以，当 $d > \frac{{(k + 1)}^{2}}{4}$ 时， $W (G^{'}) > W (G)$ 。

当 $l_{i} = l_{j} = l$ ， $n_{i} = n_{j} + 1 = n + 1$ 时， $2 n + 1 + n (C^{'}) = 2 d + 1$ 时，则有 $\begin{matrix} Δ W = (l - 1) (\frac{1}{3} l^{2} - \frac{1}{6} l + d l - 2 n^{2} - 2 n) - 2 > \frac{1}{3} \times 2^{2} - \frac{1}{6} \times 2 + 2 d - 2 n^{2} - 2 n - 2 \\ > - 2 \times {(\frac{k - 1}{2})}^{2} - 2 \times \frac{k - 1}{2} + 2 \times \frac{{(k + 1)}^{2}}{4} - 1 = k > 0 \end{matrix}$ 。所以，当 $d > \frac{{(k + 1)}^{2}}{4}$ 时， $W (G^{'}) > W (G)$ 。

2.5. 结论1 (扫帚变换)

令图G为一个阶为 $2 d + 1$ ，直径为d的单圈图，圈C是图G的一个阶为 $2 d + 1 - k$ 的子图。通过以下步骤可以将单圈图G中链接在圈C上的任意一支树 $T_{i}$ 变成扫帚树，使得Wiener指标增加。令 $T_{i}$ 与圈C链接于圈上的点 $u_{i}$ 。

第一步：当 $d > k$ 时，反复进行引理2中的变换，直到 $T_{i}$ 的所有悬挂点都与顶点 $u_{i}$ 的距离相等，在此过程中G的Wiener指标不断增大。

第二步：由引理3可知，当 $d > k$ 时，任意选取两个扫帚树 $B (n_{i}, l_{i}), B (n_{j}, l_{j}) \subset T_{i}$ 满足条件： $l_{i} = l_{j}$ 和 $n_{i} - n_{j} \geq 0$ ，通过反复进行将 $B (n_{i}, l_{i})$ 和 $B (n_{j}, l_{j})$ 变为 $B (n_{i} - 1, l_{i})$ 和 $B (n_{j} + 1, l_{j})$ 的变化，我们可以不断增加Wiener指标，直到 ${n^{'}}_{i} = {n^{'}}_{j}$ 或者 ${n^{'}}_{i} = {n^{'}}_{j} + 1$ 。再根据引理4，当 $d > \frac{{(k + 1)}^{2}}{4}$ 时，将 $B ({n^{'}}_{i}, l_{i})$ 和 $B ({n^{'}}_{j}, l_{j})$ 变为 $B ({n^{'}}_{i} + {n^{'}}_{j}, l_{i})$ ，此过程中G的Wiener指标不断增大，反复步骤二直至 $T_{i}$ 变成扫帚树。

2.6. 引理5 [8]

阶为m的圈C上的一个顶点u到圈上其他各点的距离和为：

$d_{C_{m}} (u) = {\begin{cases} \frac{1}{4} m^{2} (当 m 是偶数) \\ \frac{1}{4} (m^{2} - 1) (当 m 是奇数) \end{cases}$

阶为m的圈C的Wiener指标为：

$W (c_{m}) = {\begin{cases} \frac{1}{8} m^{3} (当 m 是偶数) \\ \frac{1}{8} m (m^{2} - 1) (当 m 是奇数) \end{cases}$

2.7. 引理6

令图G是一个阶为 $2 d + 1$ ，直径为d的单圈图，圈C是图G的一个阶为 $2 d + 1 - k$ 的子图。在单圈图G上有扫帚树 $B (n_{i}, l_{i})$ 链接在圈C上的点 $u_{i}$ 上。令 $G^{'} = G - v_{i, l_{i} - 1} v_{i, l_{i} - 2} + v_{i, l_{i} - 2} v_{i, l_{i}}$ ，当 $d > k$ 时，有 $W (G^{'}) \geq W (G)$ 。

证明：令 $G^{'} = G - v_{i, l_{i} - 1} v_{i, l_{i} - 2} + v_{i, l_{i} - 2} v_{i, l_{i}}$ ，有 $Δ W = W (G^{'}) - W (G) = (n_{i} - l_{i}) (2 d - n_{i} + l_{i} - 1)$ 。

当 $d > k$ 时，有 $Δ W > 0$ ，即 $W (G^{'}) > W (G)$ 。

2.8. 引理7

在图 $G = G_{d, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k}))$ 中，令集合 $P = {P \subset G_{d, i} (2 d + 1)}$ ，图中必定存在一支中心扫帚树 $B (n_{i}, l_{i})$ 有 $B (n_{i}, l_{i}) \in \cap P (i, j)$ 。若不存在，必定可以通过引理6获得一个存在中心扫帚树且Wiener指标更大的图 $G^{'}$ 。

证明：当 $i = 1$ 时，令唯一的一支扫帚树为中心扫帚树。

当 $i > 1$ 时，若集合 $P = {P \in G_{d, i} (2 d + 1)}$ 中不存在 $P (i, j)$ ，反复通过引理6中的变化，我们必定可以得到一个有更大Wiener指标，且集合 $P = {P \in G_{d, i} (2 d + 1)}$ 不为空的情况。

当集合 $P$ 中只有一个 $P (i, j)$ ，则令 $P (i, j)$ 上两支扫帚树中直径较大的一支为中心扫帚树。

当集合 $P$ 中有两个或以上 $P (i, j)$ ，如果不存在 $B (n_{i}, l_{i}) \in \cap P (i, j)$ ，我们将情况分为以下三种：

情况1：在图 $G_{d, 4} (2 d + 1)$ 中，将扫帚树任意标为 $B (n_{a}, l_{a})$ ， $B (n_{b}, l_{b})$ ， $B (n_{c}, l_{c})$ 和 $B (n_{d}, l_{d})$ ，若存在 $P (a, c)$ 和 $P (b, d)$ ，且 $n_{a} \geq n_{c}$ ， $n_{b} \geq n_{d}$ ，我们可以得出： $l_{b} + l_{d} \geq \frac{k - 1}{2}$ ， $l_{a} + l_{c} \geq \frac{k - 1}{2}$ ， $l_{a} + l_{b} + l_{c} + l_{d} \leq k$ 。因此，我们可以得到： $l_{a} + l_{c} = \frac{k - 1}{2}$ 且 $l_{b} + l_{d} = \frac{k + 1}{2}$ ；或者 $l_{a} + l_{c} = l_{b} + l_{d} = \frac{k - 1}{2}$ 。此时令 $B (n_{b}, l_{b})$ 与 $B (n_{d}, l_{d})$ 中直径较大的一支为中心扫帚树。

情况2：在图 $G_{d, 5} (2 d + 1)$ 中，将扫帚树顺时针标为 $B (n_{a}, l_{a})$ ， $B (n_{b}, l_{b})$ ， $B (n_{c}, l_{c})$ ， $B (n_{d}, l_{d})$ 和 $B (n_{e}, l_{e})$ 。显然该图可以被刻画为： $l_{a} + l_{c} = l_{b} + l_{d} = \frac{k - 1}{2}$ ， $l_{e} = n_{e} = 1$ 。假设 $n_{a} + n_{b} \geq n_{c} + n_{d}$ 。令 $G^{'} = G - B (n_{e}, l_{e}) + B (n_{e - 1}, l_{e - 1})$ 且 $n_{e} = l_{e} = n_{e - 1} = l_{e - 1} = 1$ ，很明显Wiener指标会增长，有如下 $Δ W = n_{d} (n_{a} + n_{b} - n_{c} - n_{d}) > 0$ 。因此总存在一个有着更大Wiener指标的图 $G_{d, 4} (2 d + 1)$ 存在不为空的P。

情况3：在图 $G_{d, i} (2 d + 1)$ ， $i > 5$ ，将扫帚树顺时针标为 $B (n_{a}, l_{a})$ ， $B (n_{b}, l_{b})$ ， $B (n_{c}, l_{c})$ ， $B (n_{d}, l_{d})$ 等，假设存在 $P (a, c)$ 和 $P (b, d)$ ，我们可以得到 $l_{a} + l_{c} \geq \frac{k - 1}{2}$ 且 $l_{b} + l_{d} \geq \frac{k - 1}{2}$ ， $l_{a} + l_{b} + l_{c} + l_{d} \leq k - 2$ ，条件相互矛盾，因此不可能存在不包含中心扫帚树的P，该情况不存在。

2.9. 引理8

在图 $G = G_{d, i} (2 d + 1)$ 中， $i \geq 1$ ， $k \geq 1$ ，则存在一个图 $G^{'} = G_{d, i - 1} (2 d + 1)$ ，其中 $n (B (n_{i}, l_{i})) \geq 0$ ，当 $d \geq \frac{9 k}{2}$ ，有 $W (G^{'}) \geq W (G)$ 。

证明：任意选取一支扫帚树记为 $B (n_{0}, l_{0})$ 。如图5， $B (n_{0}, l_{0})$ 链接于圈C上顶点 $u_{0}$ ，从 $u_{0}$ 开始将圈上的顶点顺时针(或逆时针)记为 $u_{1}, u_{2}, \dots, u_{2 d - k}$ 。 $v_{0, 1}$ 和 $v_{0, 2}$ 是在 $B (n_{0}, l_{0})$ 上的两个顶点，令 ${G^{'}}_{d, i} (2 d + 1) = G_{d, i} (2 d + 1) - u_{0} u_{1} - u_{0} u_{2 d - k} - v_{0, 1} v_{0, 2} - u_{0} v_{0, 1} - v_{0, 2} v_{0, 3} + v_{0, 1} u_{0} + v_{0, 1} u_{1} + v_{0, 2} u_{0} + v_{0, 2} u_{2 d - k} + u_{0} v_{0, 3}$ 时，该图的Wiener指标会增加。

当k是奇数时， $2 d - k$ 为奇数，设 $2 m + 1 = 2 d - k$ 。

Figure 5. Lemma 8

图5. 引理8

$B (n_{j}, l_{j}) (1 \leq j \leq m - 1)$ 和 $B (n_{i}, l_{i}) (1 \leq i \leq 2 m + 1, i \neq j)$ 之间Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{j}, l_{j}), \cap_{i = 1, i \neq j}^{2 m + 1} B (n_{i}, l_{i})) = 2 n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i}$

$B (n_{0}, l_{0})$ 和 $B (n_{i}, l_{i}) (1 \leq i \leq 2 m + 1)$ 之间Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{0}, l_{0}), B (n_{i}, l_{i})) = - [\sum_{i = 1}^{2 m + 1} n_{i} (n_{0} - 1) + 2 n_{m + 1}]$

$B (n_{0}, l_{0})$ 自身Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{0}, l_{0})) = n_{0} - 1$

$B (n_{i}, l_{i}) (i = 1, 2, \dots, 2 m, 2 m + 1)$ 和圈之间Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{i}, l_{i}), C) = \sum_{i = 1}^{m} [2 (m - i) + 1] (n_{i} + n_{2 m + 2 - i}) + n_{m + 1}$

$B (n_{0}, l_{0})$ 和圈之间Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{0}, l_{0}), C) = W (C_{2 d + 3 - k}) - W (C_{2 d + 1 - k}) + d_{C_{2 d + 1 - k}} (u) + 3 (2 d + 1 - k) - (n_{0} - 2) (2 d - k + 2)$

由此，图的Wiener指标变化为：

$\begin{matrix} Δ W (G) = Δ W (B (n_{1}, l_{1}), B (n_{2}, l_{2}), \dots, B (n_{m}, l_{m}), B (n_{m + 1}, l_{m + 1}), \dots, \\ B (n_{2 m}, l_{2 m}), B (n_{2 m + 1}, l_{2 m + 1}), B (n_{0}, l_{0}), C) \\ = 2 \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i} - [\sum_{i = 1}^{2 m + 1} n_{i} (n_{0} - 1) + 2 n_{m + 1}] + (n_{0} - 1) \\ + \sum_{i = 1}^{m} [2 (m - i) + 1] (n_{i} + n_{2 m + 2 - i}) + n_{m + 1} + {\frac{{(2 d + 3 - k)}^{3}}{8} - \frac{{(2 d + 1 - k)}^{3}}{8} \\ + 2 \times \frac{{(2 d + 1 - k)}^{2}}{4} + 3 (2 d + 1 - k) - (n_{0} - 2) (2 d - k + 2)} \end{matrix}$

$\begin{array}{l} = 2 \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i} - [(k - n_{0}) (n_{0} - 1) + 2 n_{m + 1}] + (n_{0} - 1) \\ + \sum_{i = 1}^{m} [2 (m - i) + 1] (n_{i} + n_{2 m + 2 - i}) + n_{m + 1} + \frac{{(2 m + 4)}^{3}}{8} - \frac{{(2 m + 2)}^{3}}{8} \\ - 2 \times \frac{{(2 m + 2)}^{2}}{4} - (n_{0} + 1) (2 d + 1 - k) - (n_{0} - 2) \end{array}$

$\begin{array}{l} = 2 \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i} + \sum_{i = 1}^{m} [2 (m - i) + 1] (n_{i} + n_{2 m + 2 - i}) - (k - n_{0}) (n_{0} - 1) \\ + m^{2} + 5 m + 5 + [(n_{0} - 1) - (2 n_{0})] (2 d + 1 - k) - n_{m + 1} + 1 \\ > (n_{0} - 1) (2 d + n_{0} - 2 k + 1) + m^{2} + 5 m + 6 - 2 k \times (2 m + 2) - k \\ > (m + 1) (m - 4 k + 2) + 2 m - k + 4 \end{array}$

当 $d \geq \frac{9 k}{2}$ ， $m - 4 k + 2 = d - \frac{9 k}{2} + \frac{3}{2} > 0$ ，有 $Δ W (G) > 0$ 。

当 $l_{0} \geq 3$ 时，该图的Wiener指标会不断增加。

当k是偶数时， $2 d - k$ 为偶数，设 $2 m = 2 d - k$ 。

就如同奇数情况下，图的Wiener指标变化为：

$\begin{array}{l} Δ W (G) = Δ W (B (n_{1}, l_{1}), B (n_{2}, l_{2}), \dots, B (n_{m}, l_{m}), B (n_{m + 1}, l_{m + 1}), \dots, \\ B (n_{2 m}, l_{2 m}), B (n_{0}, l_{0}) - v_{0, l_{0}} - v_{0, l_{0} + 1}, v_{0, l_{0}}, v_{0, l_{0} + 1}, C) \\ = \sum_{j = 1}^{m - 1} n_{j} (2 \sum_{i = m + 1 + j}^{2 m} n_{i} + n_{m + 1 + j}) - \sum_{i = 1}^{2 m} n_{i} (n_{0} - 1) + (n_{0} - 1) + \sum_{i = 1}^{m} (2 m - 2 i) (n_{i} + n_{2 m + 1 - i}) \\ + {\frac{{(2 d + 3 - k)}^{3} - (2 d + 3 - k)}{8} - [\frac{{(2 d + 1 - k)}^{3} - (2 d + 1 - k)}{8} \\ + 2 \times \frac{{(2 d + 1 - k)}^{2} - 1}{4} + 3 (2 d + 1 - k)] - (n_{0} - 2) (2 d - k + 2)} \end{array}$

$\begin{array}{l} > \sum_{j = 1}^{m - 1} n_{j} (2 \sum_{i = m + 1 + j}^{2 m} n_{i} + n_{m + 1 + j}) + \sum_{i = 1}^{m} (2 m - 2 i) (n_{i} + n_{2 m + 1 - i}) \\ + (2 d - 2 k + n_{0} + 1) (n_{0} - 1) + m^{2} + 4 m + 4 - 2 k \times (2 m + 1) \\ > (m + 1) (m - 4 k + 3) + 1 \end{array}$

当 $d \geq \frac{9 k}{2}$ ， $m - 4 k + 3 = d - \frac{9 k}{2} + 3 > 0$ ，有 $Δ W (G) > 0$ 。

当 $l_{0} \geq 3$ 时，该图的Wiener指标会不断增加。

根据引理7，存在一支中心扫帚树 $B (n_{i}, l_{i})$ ，我们将它标为 $B (n_{0}, l_{0})$ ，从它开始将图上扫帚树顺时针依次标为 $B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k})$ ，可以找到一支顶点数不为0的 $B (n_{i}, l_{i})$ 满足： $d_{G} (u_{i}, u_{0}) = \max d_{G} (u_{j}, u_{0})$ ， $(1 \leq j \leq 2 d - k)$ ，我们将图上扫帚树和圈上的点重新标记，将 $B (n_{i}, l_{i})$ 记为 $B (n_{0}, l_{0})$ (特别地，当 $i = 1$ 时，将中心扫帚树记为 $B (n_{0}, l_{0})$ )， $B (n_{0}, l_{0})$ 链接在圈C上的顶点为 $u_{0}$ ，从 $u_{0}$ 开始将圈上的顶点顺时针(或逆时针)记为 $u_{1}, u_{2}, \dots, u_{2 d - k}$ ，将中心扫帚树记为 $B (n_{c}, l_{c})$ ，保证 $d - \frac{k}{2} \leq c \leq 2 d - k$ 。

当 $B (n_{c}, l_{c})$ 中 $l_{c} < d - d (C)$ 时，根据 $B (n_{0}, l_{0})$ 中 $l_{0}$ 的大小，分类讨论：

情况1：当 $i > 1$ ，且 $B (n_{0}, l_{0})$ 中 $l_{0} \geq 3$ 或 $n_{0} = l_{0} = 2$ 时，对 $B (n_{0}, l_{0})$ 反复上述变化。

情况2：当 $i > 1$ ，且 $B (n_{0}, l_{0})$ 中 $n_{0} > l_{0} = 2$ 时，有：

如果 $l_{c} + l_{0} + d_{G} (u_{c}, u_{0}) = d$ ，对中心扫帚树 $B (n_{c}, l_{c})$ 作一次上述变化，此时可以得到图 $G^{'} = G_{d - 1, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k + 2}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k + 2}, l_{2 d - k + 2}))$ ，且 $W (G^{'}) > W (G)$ 。

再根据引理6，令 $B (n_{0}, l_{0})$ 删去边 $v_{0, l_{0} - 1} v_{0, l_{0} - 2}$ ，加上边 $v_{0, l_{0} - 2} v_{0, l_{0}}$ ，可以得到 $G^{″} = G_{d, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k + 2}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k + 2}, l_{2 d - k + 2}))$ ，且 $W (G^{″}) > W (G^{'})$ 。根据不等式的传递性， $W (G^{″}) > W (G^{'})$ ，此时 $l_{0} = 3$ ，回到情况1。

如果 $l_{c} + l_{0} + d_{G} (u_{c}, u_{0}) < d$ ，根据引理6，令 $B (n_{0}, l_{0})$ 删去边 $v_{0, l_{0} - 1} v_{0, l_{0} - 2}$ ，加上边 $v_{0, l_{0} - 2} v_{0, l_{0}}$ ，此时 $l_{0} = 3$ ，回到情况1。

情况3：当 $i = 1$ 且 $B (n_{0}, l_{0})$ 中 $l_{0} > 1$ 时，对 $B (n_{0}, l_{0})$ 作一次上述变化，可以得到图 $G^{'} = G_{d - 1, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k + 2}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k + 2}, l_{2 d - k + 2}))$ ，且 $W (G^{'}) > W (G)$ 。

情况4：当 $B (n_{0}, l_{0})$ 中 $l_{0} = 1$ 时，见引理9，引理8得证。

当 $B (n_{c}, l_{c})$ 中 $l_{c} = d - d (C)$ 时，对中心扫帚树 $B (n_{c}, l_{c})$ 作一次上述变化，此时可以得到图 $G^{'} = G_{d - 1, i} (2 d + 1) = C_{u_{0} u_{1} \dots u_{2 d - k + 2}} (B (n_{0}, l_{0}), B (n_{1}, l_{1}), \dots, B (n_{2 d - k + 2}, l_{2 d - k + 2}))$ ，且 $W (G^{'}) > W (G)$ ，此时回到 $l_{c} < d - d (C)$ 的情况。

2.10. 引理9

如图6，在引理8中，当 $n_{0} \geq 1$ 且 $l_{0} = 1$ ， $B (n_{0}, l_{0})$ 上的悬挂点标记为 $v_{0, 1}, \dots, v_{0, n_{0}}$ ，令 ${G^{'}}_{d, i} (2 d + 1) = G_{d, i} (2 d + 1) - u_{0} u_{1} + v_{0, 1} u_{1}$ ，该图Wiener指标增大。

证明：根据引理7，存在一支中心扫帚树 $B (n_{i}, l_{i})$ ，我们将它标为 $B (n_{0}, l_{0})$ ，从它开始将图上扫帚树顺时针依次标为 $B (n_{1}, l_{1}), \dots, B (n_{2 d - k}, l_{2 d - k})$ ，可以找到一支顶点数不为0的 $B (n_{i}, l_{i})$ 满足： $d_{G} (u_{i}, u_{0}) = \max d_{G} (u_{j}, u_{0})$ ， $(1 \leq j \leq 2 d - k)$ ，我们将图上扫帚树和圈上的点重新标记，将 $B (n_{i}, l_{i})$ 记为 $B (n_{0}, l_{0})$ (特别地，当 $i = 1$ 时，将中心扫帚树记为 $B (n_{0}, l_{0})$ )， $B (n_{0}, l_{0})$ 链接在圈C上的顶点为 $u_{0}$ ，从 $u_{0}$ 开始将圈上的点顺时针(或逆时针)记为 $u_{1}, u_{2}, \dots, u_{2 d - k}$ ，将中心扫帚树记为 $B (n_{c}, l_{c})$ ，保证 $d - \frac{k}{2} \leq c \leq 2 d - k$ 。

Figure 6. Lemma 9

图6. 引理9

情况1：当k是奇数时， $2 d - k$ 为奇数，设 $2 m + 1 = 2 d - k$ 。

很明显， $B (n_{0}, l_{0})$ 和 $B (n_{i}, l_{i}), i = 1, \dots, 2 m + 1$ 之间Wiener指标变化为：

$Δ W_{G G^{'}} (B (n_{0}, l_{0}), \cap_{i = 1}^{2 m + 1} B (n_{i}, l_{i})) = \sum_{i = 1}^{m} n_{i} (n_{0} - 2) - n_{m + 1}$

$B (n_{j}, l_{j}) (1 \leq j \leq m - 1)$ 和 $B (n_{i}, l_{i}) (1 \leq i \leq 2 m + 1, i \neq j)$ 之间Wiener指标的变化为：

$Δ W_{G G^{'}} (B (n_{j}, l_{j}), \cap_{i = 1, i \neq j}^{2 m + 1} B (n_{i}, l_{i})) = n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i}$

$B (n_{i}, l_{i}) (i = 1, 2, \dots, 2 m)$ 和圈之间Wiener指标变化为：

$Δ W_{G G^{'}} (B (n_{i}, l_{i}), C) = \sum_{i = 1}^{m} [(m - i + 1) n_{i} + n_{2 m + 2 - i} (m - i)]$

$B (n_{0}, l_{0})$ 和圈之间Wiener指标变化为：

$Δ W_{G G^{'}} (C, B (n_{0}, l_{0})) = W (C_{2 d + 2 - k}) - [W (C_{2 d + 1 - k}) + d_{C_{2 d + 1 - k}} (u) + (2 d + 1 - k)] + m (n_{0} - 1)$

由此，该图的Wiener指标变化有：

$\begin{matrix} Δ W (G) = Δ W (B (n_{1}, l_{1}), B (n_{2}, l_{2}), \dots, B (n_{m}, l_{m}), B (n_{m + 1}, l_{m + 1}), \dots, \\ B (n_{2 m}, l_{2 m}), B (n_{2 m + 1}, l_{2 m + 1}), B (n_{0}, l_{0}), C) \\ = \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i} + (n_{0} - 2) \sum_{i = 1}^{m} n_{i} - n_{m + 1} + \sum_{i = 1}^{m} [(m - i + 1) n_{i} + (m - i) n_{2 m + 2 - i}] \\ + {\frac{{(2 d + 2 - k)}^{3} - (2 d + 2 - k)}{8} - [\frac{{(2 d + 1 - k)}^{3}}{8} \\ + \frac{{(2 d + 1 - k)}^{2}}{4} + (2 d + 1 - k)]} + (n_{0} - 1) m \end{matrix}$

$\begin{array}{l} > \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + j + 2}^{2 m + 1} n_{i} - (k - 1) + \sum_{i = 1}^{m} (m - i + 1) n_{i} + \sum_{i = m + 1}^{2 m + 1} (m - i) n_{2 m + 2 - i} \\ + {\frac{{(2 m + 3)}^{3} - (2 m + 3)}{8} - [\frac{{(2 m + 2)}^{3}}{8} + \frac{{(2 m + 2)}^{2}}{4} + (2 m + 2)]} \\ > - (k - 1) + \frac{m^{2} - m - 2}{2} = \frac{m^{2} - m}{2} - k \end{array}$

当 $d \geq \frac{9 k}{2}$ ， $\frac{m^{2} - m}{2} - k > 0$ ，有 $Δ W (G) > 0$ 。

情况2：当k是偶数时， $2 d - k$ 为偶数，设 $2 m = 2 d - k$ 。

与奇数情况类似，该图的Wiener指标变化有：

$\begin{matrix} Δ W (G) = Δ W (B (n_{1}, l_{1}), B (n_{2}, l_{2}), \dots, B (n_{m}, l_{m}), B (n_{m + 1}, l_{m + 1}), \dots, \\ B (n_{2 m}, l_{2 m}), B (n_{2 m}, l_{2 m}), B (n_{0}, l_{0}), C) \\ = \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + 1 + j}^{2 m} n_{i} + (n_{0} - 2) \sum_{i = 1}^{m} n_{i} + \sum_{i = 1}^{m} [(m - i + 1) n_{i} + (m - i) n_{2 m + 1 - i}] \\ + (n_{0} - 1) m + {\frac{{(2 d + 2 - k)}^{3}}{8} - [\frac{{(2 d + 1 - k)}^{3} - (2 d + 1 - k)}{8} \\ + \frac{{(2 d + 1 - k)}^{2}}{4} + (2 d + 1 - k)]} \end{matrix}$

$\begin{array}{l} > \sum_{j = 1}^{m - 1} n_{j} \sum_{i = m + 1 + j}^{2 m} n_{i} - \sum_{i = 1}^{m} n_{i} + \sum_{i = 1}^{m} (m - i + 1) n_{i} + \sum_{i = 1}^{m} (m - i) n_{2 m + 1 - i} \\ + {\frac{{(2 d + 2 - k)}^{3}}{8} - [\frac{{(2 d + 1 - k)}^{3} - (2 d + 1 - k)}{8} \\ + \frac{{(2 d + 1 - k)}^{2}}{4} + (2 d + 1 - k)]} \\ > \frac{m^{2} - m - 1}{2} - k \end{array}$

当 $d \geq \frac{9 k}{2}$ 时， $\frac{m^{2} - m - 1}{2} - k > 0$ ，有 $Δ W (G) > 0$ 。

3. 定理1的证明

为了证明定理1，我们需要刻画阶为 $2 d + 1$ ，直径为d的单圈图的图形。令圈上的顶点数为 $2 d + 1 - k$ 。根据结论1，我们可以证明当 $d > \frac{{(k + 1)}^{2}}{4}$ 时，在任意阶为 $2 d + 1$ ，直径为d的单圈图中，具有最大的Wiener指标的图可以被刻画为 $G_{d, i} (2 d + 1)$ ，其中 $0 \leq i \leq k \leq d$ 。

此时根据引理7，我们可以确定一个中心扫帚树的存在。根据引理8，我们可以知道当 $d \geq \frac{9 k}{2}$ 时，对于任意的图 $G = G_{d, i} (2 d + 1)$ 必定存在着一个具有更大Wiener指标的图 $G^{'} = G_{d, i - 1} (2 d + 1)$ ，依次推理，当 $i = 0$ 时，图G变为圈 $C = u_{0} u_{1} u_{2} \dots u_{2 d} u_{0}$ 。

因此，在阶为 $2 d + 1$ ，直径为d的单圈图中，具有最大Wiener指标的图可以被刻画为圈 $C = u_{0} u_{1} u_{2} \dots u_{2 d} u_{0}$ ，即定理1得证。

致谢

本论文历经6个月时间完成，在研究与写作途中有许多的障碍与困难，但是都在老师与同学们的帮助下度过。在此我们诚挚感谢我们的论文指导老师，因为老师的悉心指导与不断督促，我们才能在课题研究与论文写作上不断精益求精。同时也感谢本文所涉及到的各位专家学者，本文很多的思路与启发都是来自于各个学者的研究文献。最后感谢我的同学们，本文是我们共同完成，一同创作的结果。本文因我们学术水平有限，该论文仍有不足之处，恳请各位学者与学友批评指正。

基金项目

扬州大学大学生科创基金项目，本项目得到“江苏高校品牌专业建设工程资助项目(数学与应用数学，PPZY2015B109)”经费资助，同时也得到国家自然科学基金项目(基金号：11801494)的资助。

文章引用

王惠敏,王元培,曹陈琛,孙强. 给定直径和阶的具有最大Wiener指标的单圈图
The Maximal Wiener Index of UnicyclicGraph with Given Diameter and Order[J]. 应用数学进展, 2020, 09(03): 318-329. https://doi.org/10.12677/AAM.2020.93038

参考文献

1. DeLaVina, E. and Waller, B. (2008) Spanning Trees with Many Leaves and Average Distances. Electronic Journal of Combinatorics, 15, 16. https://doi.org/10.37236/757

2. Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20. https://doi.org/10.1021/ja01193a005

3. Entringer, R.C., Jackson, D.E. and Snyder, D.A. (1976) Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296.

4. Bondy, J.A. and Murty, U. (2008) Graph Theory. Graduate Texts in Mathematics. 5th Edition, Springer, New York. https://doi.org/10.1007/978-1-84628-970-5

5. Broersma, H. and Tuinstra, H. (1998) Independent Trees and Hamilton Cycles. Journal of Graph Theory, 29, 227-237. https://doi.org/10.1002/(SICI)1097-0118(199812)29:4<227::AID-JGT2>3.0.CO;2-W

6. Du, Z. and Zhou, B. (2010) Minimum on Wiener Indices of Trees and Unicyclic Graphs of the Given Matching Number. MATCH Commu-nications in Mathematical and in Computer Chemistry, 63, 101-112.

7. Yu, G. and Feng, L. (2010) On the Wiener Index of Unicyclic Graphs with Given Girth. Ars Combinatoria, 94, 361-369.

8. 汤自凯. 具有次大Wiener指数的单圈图[J]. 湖南文理学院学报(自然科学版), 2006, 18(4): 2-5.

NOTES

^*通讯作者。

期刊菜单