给定团数的Wiener指数极图

doi:10.12677/AAM.2019.86134

期刊菜单

给定团数的Wiener指数极图
On the Extremal Wiener Indices of Graphs with Given Clique Number

DOI: 10.12677/AAM.2019.86134, PDF, HTML, XML, 下载: 949 浏览: 4,115 科研立项经费支持
作者: 陈员龙, 吴小英：广东金融学院金融数学与统计学院，广东广州
关键词: 图；Wiener指数；极图；团数；Graph； Wiener Index； Extremal Graphs； Clique Number

摘要: 本文研究一类给定团数的连通图的Wiener指数，讨论和刻画了团数为l的n阶连通图的Wiener指数的上界和下界，通过移接变形等方法证明了团数为l的n阶连通图中具有最大，最小Wiener指数的极值图分别为K_luP_n-l+1与Tuŕan图。

Abstract: In this paper, we investigate the Wiener index for connected graphs of given clique number, obtain sharp lower and upper bounds on Wiener index for connected graphs of order n with clique number l. For connected graphs of order n with clique number l, by the method of shift-joint deformation, we obtain the largest Wiener index graph and the smallest Wiener index graph are K_luP_n-l+1 and Tuŕan graph, respectively.

文章引用：陈员龙, 吴小英. 给定团数的Wiener指数极图[J]. 应用数学进展, 2019, 8(6): 1160-1165. https://doi.org/10.12677/AAM.2019.86134

1. 引言

分子拓扑学是一门应用于图论、化学、拓扑学等相互交叉的学科，是当前的一个热门研究领域。分分子拓扑学的一个最重要研究方向是分子拓扑指数，其中关于拓扑指数的极值研究为计算机搜索算法确定分子图的顶点数与边数的上下确界范围提供理论依据，从而提高计算机的搜索算法的效率。因而关于分子拓扑指数的最大或最小拓扑指数图的研究成为化学分子图的研究热点，近年来许多研究者对其进行深入研究并取得很多有意义的结果 [1] - [9] [11] [12] [13] 。

Wiener指数可以用来解释烷烃的物理化学性质的变化，分子结构与药理性能的关系，因此确定Wiener指数的极值图对分子化学应用有着非常重要的意义。早在上个世纪70年代Entringer等在 [10] 中证明了n阶树中具有最大、最小Wiener指数的极值图分别是路 $P_{n}$ 与星图 $S_{n}$ 。随后出现许多关于Wiener指数的数学与化学的结论，特别是树的Wiener指数研究。例如Jelena等在 [14] 中讨论了给定最大度的n阶树，获得此类树的最小Wiener指数极值图。刘慧清等在 [3] [4] 中分别讨论了给定直径的n阶树的最小Wiener指数极值图与及给定r个圈的n阶连通图的四类拓扑指数极值图。王华在研究给定度序列的n阶树时 [15] ，确定了最大与最小的Wiener指数极值图。Dobrynin等在 [13] 中对近年关树的Wiener指数的重要研究结果做了一个综述，并给出了几个猜想及公开问题。

本文考虑了给定团数的n阶连通图的Wiener指数的值图。通过移接变形等方法证明了团数为l的n阶连通图中具有最大，最小Wiener指数的极值图分别为 $K_{l} u P_{n - l + 1}$ 与Tuŕan图。

2. 基本引理

在这一节我们先给出一些相关引理。设 $K_{l}$ 是一个 $l (l \geq 3)$ 阶团， $V (K_{l}) = {v_{1}, v_{2}, \dots, v_{l}}$ 。设 $H (K_{l}, H) = {G : G 是一个具有团数为 l 的 n 阶简单连通图}$ ， $H (K_{l}; T_{k_{1}}, T_{k_{2}}, \dots, T_{k_{l}})$ 是一个n阶简单连通图，它是在团 $K_{l}$ 的每个顶点 $v_{i}$ 上分别附上阶为 $k_{i}$ 的树 $T_{k_{i}}$ 得到的图， $H (K_{l}; P_{k_{1}}, P_{k_{2}}, \dots, P_{k_{l}})$ 是一个n阶简单连通图，它是在团 $K_{l}$ 的每个顶点 $v_{i}$ 上分别附上阶为 $k_{i}$ 的路 $P_{k_{i}}$ 得到的图，其中 $n = \sum_{i = 1}^{l} k_{i}$ $(k_{i} \geq 1, i = 1, 2, \dots, l)$ 。记

$\begin{array}{l} H (K_{l}, T) = {H (K_{l}; T_{k_{1}}, T_{k_{2}}, \dots, T_{k_{l}}) : n = \sum_{i = 1}^{l} k_{i}, k_{i} \geq 1, i = 1, 2, \dots, l} \\ H (K_{l}, P) = {H (K_{l}; P_{k_{1}}, P_{k_{2}}, \dots, T_{k_{l}}) : n = \sum_{i = 1}^{l} k_{i}, k_{i} \geq 1, i = 1, 2, \dots, l} \end{array}$

引理1 [2] 设G是一个连通图， $G_{1}$ ， $G_{2}$ 是G的两个连通子图并且有唯一的公共点u， $G_{1} \cup G_{2} = G$ 。设 $n_{1} = | V (G_{1}) |$ ， $n_{2} = | V (G_{2}) |$ 。那么 $W (G) = W (G_{1}) + W (G_{2}) + (n_{1} - 1) D_{G_{2}} (u) + (n_{2} - 1) D_{G_{1}} (u)$ 。

引理2设 $T_{n}$ ， $P_{n}$ 分别是阶为n的树和路。 $P_{k}$ 是 $T_{n}$ 中最长的一条路。如果 $u \in V (P_{k})$ 且 $d_{T_{n}} (u) = 1$ ， $v \in V (P_{n})$ 且 $d_{p_{n}} (v) = 1$ ，那么 $D_{T_{n}} (u) \leq D_{P_{n}} (v)$ 且等号成立当且仅当 $T_{n} ≅ P_{n}$ 。

证明： $D_{T_{n}} (u) = D_{P_{k}} (u) + D_{T_{n} \ P_{k}} (u) \leq D_{P_{k}} (u) + k (n - k)$ ，

$D_{P_{n}} (v) = D_{P_{k}} (u) + D_{P_{n} \ P_{k}} (u) \geq D_{P_{k}} (u) + k (n - k)$ ，

我们有 $D_{P_{n}} (v) - D_{T_{n}} (u) \geq 0$ ，因此 $D_{T_{n}} (u) \leq D_{P_{n}} (v)$ 且等号成立当且仅当 $T_{n} ≅ P_{n}$ 。

设图 $H_{1}$ ， $H_{2}$ 是两个连通图且 $V (H_{1}) \cap V (H_{2}) = {v}$ 。 $G = H_{1} v H_{2}$ 是一个连通图且

$V (G) = V (H_{1}) \cup V (H_{2})$ ， $V (H_{1}) \cap V (H_{2}) = {v}$ ， $E (G) = E (H_{1}) \cup E (H_{2})$ 。

引理3 [13] 设 $T, P$ 分别是阶为n的树和路，那么 $W (T) \leq W (P)$ 且等号成立当且仅当 $T ≅ P$ 。

引理4 设H是阶为 $n - k$ 的连通图， $T_{k + 1}$ 是一棵阶为 $k + 1$ 的树， $P_{k + 1}$ 是一条阶为 $k + 1$ 的路且 $V (H) \cap V (T_{k + 1}) = {u}$ ， $V (H) \cap V (P_{k + 1}) = {u}$ ，则 $W (H u T_{k + 1}) \leq W (H u P_{k + 1})$ 且等号成立当且仅当 $T_{k + 1} ≅ P_{k + 1}$ 。

证明：由引理1有 $W (H u T_{k + 1}) - W (H u P_{k + 1}) = W (T_{k + 1}) - W (P_{k + 1}) + k (D_{T_{k + 1}} (u) - D_{P_{k + 1}} (u))$ ，根据引理2，3有 $W (H u T_{k + 1}) - W (H u P_{k + 1}) \leq 0$ ，因此 $W (H u T_{k + 1}) \leq W (H u P_{k + 1})$ 且等号成立当且仅当 $T_{k + 1} ≅ P_{k + 1}$ 。

由Wiener指数的定义我们有

引理5 设G是一个简单连通图且 $x, y \in V (G)$ 。如果边 $x y \notin E (G)$ ，那么。

由引理5我们有

引理6 设 $G \in H (K_{l}, T) (l \geq 3)$ 且 $x \in V (T_{i}), y \in V (T_{j}), i, j = 1, 2, \dots, l$ ，如果 $x y \notin E (G)$ ，那么 $G^{'} = G + x y \in H (K_{l}, H)$ 且 $W (G) > W (G^{'})$ ，其中 $G + x y$ 表示添加一条连接图G中不相邻的两点 $x, y$ 的边得到的图。

引理7 设 $G_{1} \in H (K_{l}, P)$ ， $P_{k_{i}}, P_{k_{j}}$ 分别是阶为 $k_{i}, k_{j} \geq 2$ 的两条不同的路。

$H = G_{1} \ ((P_{k_{i}} - {v_{i}}) \cup (P_{k_{j}} - {v_{j}})), G_{2} = H v_{i} P_{k_{i}} w P_{k_{j}}$ (见图1)。则 $W (G_{2}) > W (G_{1})$ 。

Figure 1. Two graphs

图1. 两种图例

证明：由引理1我们有

$W (G_{1}) = W (P_{k_{i}} v_{i} H) + W (P_{k_{j}}) + (n_{P_{k_{i}} v_{i} H} - 1) D_{P_{k_{j}}} (v_{j}) + (k_{j} - 1) D_{P_{k_{i}} v_{i} H} (v_{j})$ ，

$W (G_{2}) = W (H v_{i} P_{k_{i}}) + W (P_{k_{j}}) + (n_{H v_{i} P_{k_{i}}} - 1) D_{P_{k_{j}}} (w) + (k_{j} - 1) D_{H v_{i} P_{k_{i}}} (w)$ 。

直接计算有

$\begin{matrix} D_{H v_{i} P_{k_{i}}} (w) = D_{H \ {v_{i}}} (w) + D_{P_{k_{i}}} (w) \\ = D_{H \ {v_{i}}} (v_{i}) + (k_{i} - 1) (n_{H} - 1) + D_{P_{k_{i}}} (v_{i}) \\ = D_{H \ {v_{i}}} (v_{i}) + (k_{i} - 1) (n_{H} - 1) + D_{P_{_{k_{i}}}} (v_{j}) - k_{i} \\ = D_{H \ {v_{i}, v_{j}}} (v_{j}) + d_{H (v_{i}, v_{j})} + (k_{i} - 1) (n_{H} - 1) + D_{P_{_{k_{i}}}} (v_{j}) - k_{i} \\ = D_{H \ {v_{i}}} (v_{j}) + 1 + (k_{i} - 1) (n_{H} - 1) + D_{P_{_{k_{i}}}} (v_{j}) - k_{i} \\ = D_{H \ {v_{i}}} (v_{j}) + (k_{i} - 1) (n_{H} - 2) + D_{P_{_{k_{i}}}} (vj) \end{matrix}$

$D_{H v_{i} P_{k_{i}}} (v_{j}) = D_{H \ {v_{i}}} (v_{j}) + D_{P_{k_{i}}} (vj)$

因为 $K_{l} \subseteq H (l \geq 3)$ ，所以 $n_{H} \geq 3$ 。因此 $D_{H v_{i} P_{k_{i}}} (w) - D_{P_{k_{i}} v_{i} H} (v_{j}) = (k_{i} - 1) (n_{H} - 1) > 0$ ，也即 $D_{H v_{i} P_{k_{i}}} (w) > D_{P_{k_{i}} v_{i} H} (v_{j})$ 。又因为 $D_{P_{k_{j}}} (w) = D_{P_{k_{j}}} (v_{j})$ ， $H v_{i} P_{k_{i}} ≅ P_{k_{i}} v_{i} H$ ，所以

$W (G_{2}) - W (G_{1}) = (n_{H v_{i} P_{k_{i}}} - 1) D_{P_{k_{j}}} (v_{j}) + (k_{j} - 1) (D_{H v_{i} P_{k_{i}}} (w) - D_{P_{k_{i}} v_{i} H} (v_{j})) > 0$

故 $W (G_{2}) > W (G_{1})$ 。

3. 项给定团数的图的Wiener指数极图

定理 1设 $G \in H (K_{l}, H)$ ，那么 $W (G) \leq W (K_{l} u P_{n - l + 1})$ 且等号成立当且仅当 $G ≅ K_{l} u P_{n - l + 1}$ 。

证明：我们选择 $G \in H (K_{l}, H)$ 使得 $W (G)$ 尽可能大。

断言1 如果 $G \in H (K_{l}, H)$ 是具有最大Wiener指数的图，那么 $G \in H (K_{l}, T)$ 。

断言1的证明：否则，我们假设 $G \notin H (K_{l}, T)$ ，那么存在一个圈 $C \subseteq G$ 且有 $x y \in E (C)$ ，但 $x y \notin E (K_{l})$ 。设 $G^{'} = G \ x y$ 为图G删除边xy那么 $G^{'} \in H (K_{l}, H)$ 。由引理6有。这与G的选择矛盾，所以断言1成立。

断言2 如果 $G \in H (K_{l}, H)$ 是具有最大Wiener指数的图，那么 $G \in H (K_{l}, P)$ 。

断言2的证明：由断言1有 $G \in H (K_{l}, T)$ 。由引理4有 $G \in H (K_{l}, P)$ 。所以断言2成立。

断言3 如果 $G \in H (K_{l}, H)$ 是具有最大Wiener指数的图，那么 $G ≅ K_{l} u P_{n - l + 1}$ 。

断言3的证明：否则，我们假设G不同构 $K_{l} u P_{n - l + 1}$ 。由断言2有 $G \in H (K_{l}, P)$ 。设 $V (K_{l}) = {v_{1}, v_{2}, \dots, v_{l}}$ ， $G = H (K_{l}; P_{k_{1}}, P_{k_{2}}, \dots, P_{k_{l}})$ 。那么G至少有两条阶大于1的路 $P_{k_{i}}, P_{k_{j}}$ 附在团 $K_{l}$ 的两个不同的顶点 $v_{i}, v_{j} (1 \leq i \neq j \leq l)$ 上。令 $H = G \ ((P_{k_{i}} - {v_{i}}) \cup (P_{k_{j}} - {v_{j}}))$ ， $G_{2} = H v_{i} P_{k_{i}} w P_{k_{j}}$ $G_{1} = P_{k_{i}} v_{i} H v_{j} P_{k_{j}} = G$ ，由引

理7有 $W (G) = W (G_{1}) < W (G_{2})$ 。这与G的选择矛盾，因此我们有 $G ≅ K_{l} u P_{n - l + 1}$ 。

综上所述知定理成立。

定理2 如果 $G \in H (K_{l}, H)$ 是具有最小Wiener指数的图，那么G是Tuŕan图。

证明：我们选择 $G \in H (K_{l}, H)$ 使得 $W (G)$ 尽可能小。由G的团数为l，因而G中至少有一个团 $K_{l}$ ，

不妨设为 $K_{l_{1}}$ ， $V (K_{l_{1}}) = {u_{1}, u_{2}, \dots, u_{l}}$ 。设 $G_{1} = G - V (K_{l_{1}})$ 。下面我们先证明三个断言：

断言1 在G中， $V (G_{1})$ 中每个点至多与 $V (K_{l_{1}})$ 中 $l - 1$ 个顶点都相邻。

断言1的证明：否则，G中有完全图 $K_{l + 1}$ ，与G的团数为 $l$ 矛盾，所以断言1成立。

断言2 如果 $1 \leq n - l < l$ ，则 $G_{1}$ 是一个完全图 $K_{n - l}$ 。

断言2的证明：否则，设 $G_{1}$ 中最大完全图为 $K_{r_{1}}, r_{1} < n - l$ 。由断言1知 $G_{1}$ 中每个顶点与 $K_{l_{1}}$ 中至少一个顶点距离大于等2。设 $G_{2} = G_{1} - V (K_{r_{1}})$ ，由 $K_{r_{1}}$ 为 $G_{1}$ 中最大完全图，所以 $V (G_{2})$ 中每个点至多与 $V (K_{r_{1}})$ 中 $r_{1} - 1$ 个点都相邻(否则， $G_{1}$ 中有更大的完全图，矛盾)，也即 $G_{2}$ 中每个顶点与 $K_{r_{1}}$ 中至少一个顶

点距离大于等于2。因此我们有

$W (G) \geq (\begin{matrix} n \\ 2 \end{matrix}) + n - l + n - l - r_{1} > (\begin{matrix} n \\ 2 \end{matrix}) + n - l = W (T_{l, n})$ ，

这与G的选择矛盾，所以断言2成立。

断言3 如果 $l \leq n - l$ ，则 $G_{1}$ 中含阶数最大为l的完全图 $K_{l}$ 。

断言3的证明：否则，如果 $G_{1}$ 中不含完全图 $K_{l}$ ，设 $G_{1}$ 中最大完全图为 $K_{r_{1}} (r_{1} < l)$ ，设 $G_{2} = G_{1} - V (K_{r_{1}})$ ， $G_{2}$ 中最大完全图为 $K_{r_{2}} (r_{2} \leq r_{1})$ ，依此类推，设 $G_{k} = G_{k - 1} - V (K_{r_{k - 1}})$ ， $G_{k}$ 中最大完全图为 $K_{r_{k}} (k \geq ⌊ \frac{n}{l} ⌋ + 1, r_{k} \leq r_{k - 1})$ 。由断言1知 $G_{1}$ 中每个顶点与 $K_{l_{1}}$ 中至少一个顶点的距离大于等于2，由 $K_{r_{1}}$ 为 $G_{1}$ 中最大完全图，所以 $V (G_{i} + 1)$ 中每个顶点至多与 $V (K_{r_{1}})$ 中 $r_{1} - 1$ 个点都相邻，也即 $G_{2}$ 中每个顶点与 $K_{r_{1}}$ 中至少一个顶点的距离大于等于2。依此类推，由 $K_{r_{i}}$ 为 $G_{i}$ 中最大完全图，所以 $V (G_{2})$ 中每个顶点至多与 $V (K_{r_{i}})$ 中 $r_{i} - 1$ 个顶点都相邻，也即 $G_{i + 1}$ 中每个顶点与 $K_{r_{i}}$ 中至少一个顶点的距离大于等于2，其中 $i = 1, 2, \dots, k - 1$ 。因此我们有

$\begin{matrix} W (G) \geq (\begin{matrix} n \\ 2 \end{matrix}) + n - l + n - l - r_{1} + \dots + n - l - \sum_{i = 1}^{k - 1} r_{i} \\ > (\begin{matrix} n \\ 2 \end{matrix}) + n - l + \dots + n - ⌊ \frac{n}{l} ⌋ l = W (T_{l, n}) \end{matrix}$

这与G的选择矛盾，以 $G_{1}$ 中有完全图 $K_{l}$ 。又因为G的团数为l，所以 $G_{1}$ 中含有阶数最大为l的完全图。所以断言3成立。

设 $n = t l + r (0 \leq r < l)$ ，则 $t = ⌊ \frac{n}{l} ⌋$ 。由断言3可知G中有t个顶点互不相交的l团，不妨设为 $K_{l_{1}}, K_{l_{2}}, \dots, K_{l_{t}}$ ， $V (K_{l_{1}}) = {u_{1}, u_{2}, \dots, u_{l}}$ ， $V (K_{l_{2}}) = {u_{l + 1}, u_{l + 2}, \dots, u_{2 l}}$ ，…，

$V (K_{l_{t}}) = {u_{(t - 1) l + 1}, u_{(t - 1) l + 2}, \dots, u_{t l}}$ 。

根据断言2可知G中有一个与这t个l团顶点都不相交的r团 $K_{r}$ 。

设 $V (K_{r}) = {u_{t l + 1}, u_{t l + 2}, \dots, u_{t l + r - 1}, u_{n}}$ 。下面说明这些团之间哪些顶点相邻。

(i) 对前t个l团中任意两个l团必有其中一个团的每个顶点正好与另一个团的 $l - 1$ 个顶点都相邻.根据G的团数为l，则其中任意一个团的每个顶点至多与另一个团的 $l - 1$ 个顶点都相邻。否则，G中存在阶数为 $l + 1$ 的团，这与G的团数为l矛盾。根据 $W (G)$ 尽可能小及断言3中类似分析可知，其中任意一个团的每个顶点正好与另一个团的 $l - 1$ 个顶点都相邻。

下面证明t个l团之间哪些顶点相邻。

首先我们考虑 $K_{l_{1}}$ ， $K_{l_{2}}$ 之间哪些顶点相邻。由1)知 $K_{l_{1}}$ 中每个顶点与 $K_{l_{2}}$ 中 $l - 1$ 个顶点都相邻，对于 $u_{1}$ 不失一般性可设 $u_{1} u_{l + i} \in E (G) (2 \leq i \leq l)$ ， $u_{1} u_{l + 1} \notin E (G)$ 。对于 $u_{2}$ ，必定有 $u_{2} u_{l + 1} \in E (G)$ 。否则， $u_{l + 1}$ 与 $K_{l_{1}}$ 中至多 $l - 2$ 个顶点相邻。与(i)矛盾。又因为 $u_{2}$ 与 $K_{l_{2}}$ 中 $l - 1$ 个顶点相邻，即 $u_{2}$ 与中一个顶点不相邻，不妨设为 $u_{l + 2}$ ，即 $u_{2} u_{l + 2} \notin E (G)$ 。从而 $u_{2} u_{l + i} \in E (G) (1 \leq i \neq 2 \leq l)$ 。类似讨论可设 $u_{i} u_{l + i} \notin E (G)$ ， $u_{i} u_{l + j} \in E (G) (1 \leq j \neq i \leq l)$ 。重复上面的讨论，可得 $u_{i} u_{k l + i} \notin E (G) (1 \leq k \leq t - 1)$ 。我们断言对任意 $2 \leq k \leq t - 1$ 有 $u_{l + 1} u_{k l + 1} \notin E (G)$ 。否则，因为 $u_{l + 1}$ 与 $u_{2}, u_{3}, \dots, u_{l}$ 构成一个l团， $u_{k l + 1}$ 与 $u_{2}, u_{3}, \dots, u_{l}$ 构成一个l团，所以 $u_{l + 1}$ ， $u_{k l + 1}$ 与 $u_{2}, u_{3}, \dots, u_{l}$ 构成一个 $l + 1$ 团。与G的团数为l矛盾。同理可得 $u_{l + i} u_{k l + i} \notin E (G) (2 \leq i \leq l)$ 。

重复上面的讨论，我们对这t个顶点互不相交的l团可设

$\begin{array}{l} u_{k l + i} u_{s l + i} \notin E (G) (1 \leq i \leq l, 0 \leq k \neq s \leq t - 1), \\ u_{k l + i} u_{s l + j} \in E (G) (1 \leq i \neq j \leq l, 0 \leq k \neq s \leq t - 1), \end{array}$

(ii) 类似上面的讨论，可知第 $t + 1$ 个r团 $K_{r}$ 中每个顶点正好与前t个顶点互不相交的l团 $K_{l_{i}} (1 \leq i \leq t)$

的 $l - 1$ 个顶点都相邻。不失一般性可设

$\begin{array}{l} u_{t l + i} u_{s l + i} \notin E (G) (1 \leq i \leq r, 0 \leq s \leq t - 1), \\ u_{t l + i} u_{s l + j} \in E (G) (i \neq j, 1 \leq i \leq r, 1 \leq j \leq l, 0 \leq s \leq t - 1), \end{array}$

综上可知 $u_{j}, u_{l + j}, \dots, u_{t l + j} (j = 1, 2, \dots, r)$ 构成r个顶点数为 $t + 1$ 的空图 ${\bar{K}}_{t + 1}$ ， $u_{j}, u_{l + j}, \dots, u_{(t - 1) l + j}$

$(j = r + 1, r + 2, \dots, l)$ 构成 $l - r$ 个顶点数为t的空图 ${\bar{K}}_{t}$ 。

因此图G是一个Tuŕan图 $T_{l, n}$ 。

基金项目

本文工作受到广东省自然科学基金(2017A030313037)和广东金融学院2017创新强校工程项目(20170406101, 20170502151)资助。

NOTES

^*通讯作者。

参考文献

[1]	Entringer, R. and Jackson, D. (1976) Snyder D Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296.
[2]	You, Z.-F., Huang, Y. and Du, X. (2018) A Note on Comparison between the Wiener Index and the Za-greb Indices. Communications in Mathematical Research, 34, 296-302.
[3]	Das, K.C. and Nadjafi-Arani, M.J. (2017) On Maximum Wiener Index of Trees and Graphs with Given Radius. Journal of Combinatorial Optimization, 34, 574-587. https://doi.org/10.1007/s10878-016-0092-y
[4]	Gutman, I. and Yeh, Y.N. (1995) The Sum of All Dis-tances in Bipartite Graphs. Mathematica Slovaca, 45, 327-334.
[5]	Berega, S. and Wang, H. (2007) Wiener Indices of Balanced Binary Trees. Discrete Applied Mathematics, 155, 457-467. https://doi.org/10.1016/j.dam.2006.08.003
[6]	Czabarkaě, E., Szěkely, L. and Wagner, S. (2009) The Inverse Problem for Certain Tree Parameters. Discrete Applied Mathematics, 157, 3314-3319. https://doi.org/10.1016/j.dam.2009.07.004
[7]	Li, X.L. and Wang, L. (2004) Solutions for Two Conjectures on the Inverse Problem of the Wiener Index of Peptoids. SIAM Journal on Discrete Mathematics, 17, 210-218. https://doi.org/10.1137/S0895480101387261
[8]	Wu, X.Y. and Liu, H.Q. (2010) On the Wiener Index of Graphs. Acta Applicandae Mathematicae, 110, 535-544. https://doi.org/10.1007/s10440-009-9460-2
[9]	Liu, H.Q. and Pan, X.F. (2008) Minimal Wiener Index of Trees with Fixed Diameter. MATCH Communications in Mathematical and in Computer Chemistry, 60, 85-94.
[10]	Dimitrov, D., Ikica, B. and Škrekovski, R. (2019) Maximum External Wiener Index of Graphs. Discrete Applied Mathematics, 257, 331-337. https://doi.org/10.1016/j.dam.2018.09.024
[11]	Lepovic, M. and Gutman, I. (1998) A Collective Property of Trees and Chemical Trees. Journal of Chemical Information and Modeling, 38, 823-826. https://doi.org/10.1021/ci980004b
[12]	Goldman, D., Istrail, S., Lancia, G., Piccolboni, A. and Walenz, B. (2000) Algorithmic Strategies in Combinatorial Chemistry. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 275-284.
[13]	Wagner, S. (2006) A Class of Trees and Its Wiener Index. Acta Applicandae Mathematicae, 91, 119-132. https://doi.org/10.1007/s10440-006-9026-5
[14]	Ban, Y.-E.A., Bespamyatnikh, S. and Mustafa, N.H. (2004) A Conjecture on Wiener Indices in Combinatorial Chemistry. Algorithmica, 40, 99-117. https://doi.org/10.1007/s00453-004-1097-y
[15]	Wang, H. (2008) The Extremal Values of the Wiener Index of a Tree with Given Degree Sequence. Discrete Applied Mathematics, 156, 2647-2654. https://doi.org/10.1016/j.dam.2007.11.005

为你推荐

友情链接