线图的补图的Wiener指标

doi:10.12677/AAM.2019.83063

期刊菜单

线图的补图的Wiener指标
Wiener Index of Complements of Line Graphs

DOI: 10.12677/AAM.2019.83063, PDF, HTML, XML, 国家自然科学基金支持
作者: 陈小红, 李中华, 安新慧：新疆大学，数学与系统科学学院，新疆乌鲁木齐
关键词: 线图；跳图；Wiener指标；Line Graphs； Jump Graph； Wiener Index

摘要: 令G是一个边数不小于1的图。我们称图G的线图L(G)的补图为跳图，记作J(G)。图G的Wiener指标是图G中所有点对的距离之和。在本文中，我们确定了图J(G)的Wiener指标，其中图J(G)是连通的。

Abstract: Let G be a graph of size q ≥ 1. The jump graph J(G) of G is the complement of the line graph L(G) of G. The Wiener index W(G) of G is the sum of the distances between all pairs of vertices in G. In this paper, we determine the Wiener index of J(G), where J(G) is connected.

文章引用：陈小红, 李中华, 安新慧. 线图的补图的Wiener指标[J]. 应用数学进展, 2019, 8(3): 569-574. https://doi.org/10.12677/AAM.2019.83063

1. 引言

本篇文章中所有的图都限定为无向的简单图。相关的术语和符号可以参考文献 [1] 。设

$G = (V (G), E (G))$ 是一个简单图，其中 $V (G)$ 是图G的顶点集， $E (G)$ 是图G的边集，我们分别用 $v (G)$ 和 $e (G)$ 记作 $| V (G) |$ 和 $| E (G) |$ 的阶。通常我们用 $P_{n}$ 表示阶为n的路。对于 $V (G)$ 中的每一个点v，用 $N_{G} (v)$ 表示与点v相邻的所有顶点的集合，称为v的邻点集。 $d_{G} (v) = | N_{G} (v) |$ 称为点v的度数。一般地，我们用 $H \subseteq G$ 表示H是图G的一个子图或者表示H同构于G中的一个子图。

在一个连通图G中，记 $d_{G} (u, v)$ 为G中任意两个点 $u$ 和v之间的距离（两点之间最短路的长度）， $W (G)$ 为图G的Wiener指标，定义为 $W (G) = \frac{1}{2} \sum_{u, v \in V (G)} d_{G} (u, v)$ 。

这个概念最初是由Harry Wiener在文献 [2] 中提到的。从那时起，许多研究者对Wiener指标进行了广泛的研究。关于一些Wiener指标的化学应用和数学研究的调查可以参考文献 [3] [4] 以及其中引用的参考资料。

$L (G)$ 为图G的线图，其中 $V (L (G)) = E (G)$ 并且对于任意两个点在 $L (G)$ 中相邻当且仅当这两个点对应的边在G中相邻。 $\bar{G}$ 为图G的补图，其中 $V (\bar{G}) = V (G)$ 并且对于任意两个点u和v在 $\bar{G}$ 中相邻当且仅当u和v在G中不相邻。在文献 [5] 中Chartrand等研究者称线图的补图为跳图，记作 $J (G)$ 并且给出了

一些跳图是哈密顿的充分条件。吴和孟在文献 [6] 中给出了一些哈密顿跳图的结构。我们可以在文献 [7] [8] [9] [10] 中查阅到线图的补图的更多结果。

在文献 [5] 中Chartrand等研究者证明了如果一个跳图 $J (G)$ 是连通的，则它的直径不超过4。在文献 [2] 中吴和郭给出了跳图的直径r在1到4之间的原图G的结构。在本文中，我们将根据吴和郭的结果确定连通的跳图 $J (G)$ 的Wiener指标。

2. 主要内容

2.1. 预备知识

在文献 [5] 中Chartrand等人给出了下面的结果。

定理2.1.1 [5] 如果 $J (G)$ 是连通的，则 $d i a m (J (G)) \leq 4$ 。

在文献 [2] 中吴和郭根据上面的结果给出了下面的定理。

定理2.1.2 [2] 对于一个边数不小于1的图G，如果 $J (G)$ 是连通的，则：

1) $d i a m (J (G)) = 1$ 当且仅当 $Δ (J (G)) = 1$ ；

2) $d i a m (J (G)) = 4$ 当且仅当：

a) G包含一个子图 $C_{4}^{+}$ ， $C_{4}^{+}$ 是由给 $C_{4} (V (C_{4}) = {u, v, w, x})$ 中的点u加一个新的邻点，

b) 如果G中存在一条边关联v或x，则这条边必须是vx。此外，如果 $u, w \in E (G)$ ，则 $v x \in E (G)$ ，

c) G中任意一条除 $C_{4}$ 以外的边都与u关联；

3) $d i a m (J (G)) = 3$ 当且仅当：

a) G包含 $P_{5}$ ，

b) 对于G中任意一条不在 $P_{5}$ 上的边必有一个端点在 $P_{5}$ 的2度顶点上，

c) 同时G不满足(2)中的情况；

4) $d i a m (J (G)) = 2$ ，其他。

在本文，我们主要根据上面对线图的补图的刻画来计算线图的补图的Wiener指标。

2.2. 直径小于等于2

引理2.2.1 如果 $d i a m (J (G)) \leq 2$ ， $e (G) = m$ ， $v (G) = n$ ，则 $W (G) = n (n - 1) - m$ 。

证明：因为 $d i a m (J (G)) \leq 2$ ，所以对于任意的点 $u, v \in V (G)$ ，u和v之间的距离为1或2。因此

$W (G) = m + 2 ((\begin{matrix} n \\ 2 \end{matrix}) - m) = n (n - 1) - m$ .

定理2.2.2对于一个边数为m的图G，如果 $d i a m (J (G)) \leq 2$ ，则

$W (J (G)) = \frac{1}{2} m (m - 3) + \frac{1}{2} \sum_{v \in V (G)} d_{G}^{2} (v)$

证明：因为 $e (J (G)) + e (L (G)) = (\begin{matrix} m \\ 2 \end{matrix})$ ，所以

$e (J (G)) = (\begin{matrix} m \\ 2 \end{matrix}) - e (L (G)) = \frac{1}{2} m (m - 1) - e (L (G))$ ,

其中 $e (L (G)) = \sum_{v \in V (G)} (\begin{matrix} d_{G} (v) \\ 2 \end{matrix}) = \frac{1}{2} \sum_{v \in V (G)} (d_{G}^{2} (v) - d_{G} (v)) = \frac{1}{2} \sum_{v \in V (G)} d_{G}^{2} (v) - m$ 。

所以由引理2.2.1知：

$\begin{matrix} W (J (G)) = m (m - 1) - e (J (G)) = \frac{1}{2} m (m - 1) + e (L (G)) \\ = \frac{1}{2} m (m - 3) + \frac{1}{2} \sum_{v \in V (G)} d_{G}^{2} (v) \end{matrix}$ .

2.3. 直径等于3

由定理2.1.2知：当 $d i a m (J (G)) = 3$ ，则图G的结构如图1所示。

令 $V^{'}$ 和 $E^{'}$ 分别作为 $P_{5}$ 的顶点集和边集，且 $V^{'} = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}}$ ， $E^{'} = {e_{1}, e_{2}, e_{3}, e_{4}}$ 。假设 $d_{G} (v_{2}) = d_{2} + 2$ ， $d_{G} (v_{3}) = d_{3} + 2$ ， $d_{G} (v_{4}) = d_{4} + 2$ 并且 $| N_{G} (v_{2}) n \cap N_{G} (v_{3}) | = n_{1}$ ， $| N_{G} (v_{3}) n \cap N_{G} (v_{4}) | = n_{2}$ ， $| N_{G} (v_{2}) n \cap N_{G} (v_{4}) | = n_{3}$ ，显然 $n_{1} \leq \min {d_{2}, d_{3}}$ ， $n_{2} \leq \min {d_{3}, d_{4}}$ ， $n_{3} \leq \min {d_{2}, d_{4}}$ 。

定理2.3.1对于一个边数为m的图G，如果 $d i a m (J (G)) = 3$ ，则

$\begin{matrix} W (J (G)) = d_{2}^{2} + d_{3}^{2} + d_{4}^{2} + d_{2} d_{3} + d_{3} d_{4} + d_{2} d_{4} + 5 (m - 4) \\ - (n_{1}^{2} + n_{2}^{2} + n_{3}^{2}) + 2 (n_{1} + n_{2}) + 2 n_{3} + 10 \end{matrix}$ ,

其中 $m - 4 = d_{2} + d_{3} + d_{4}$ 且 $n_{1} + n_{2} + n_{3} \leq m - 4$ 。

Figure 1. $P_{5}^{+}$

图1. $P_{5}^{+}$

证明：首先 $W (J (P_{5})) = W (P_{4}) = 10$ 。

如果 $G \neq P_{5}$ ，对于任意边 $v_{i} x \in E (G) (i = 2, 3, 4)$ 且 $x \notin V^{'}$ ，则在 $J (G)$ 中 $v_{i} x$ 到 $v_{1} v_{2}$ ， $v_{2} v_{3}$ ， $v_{3} v_{4}$ ， $v_{4} v_{5}$ 的距离之和为6。令 $S = V (G) \ V^{'}$ 且 $M = E (G) \ E^{'}$ 。有

$W (J (G)) = W (J (P_{5})) + 6 (m - 4) + W (M)$ ,

其中 $W (M) = \sum_{i, j \in {2, 3, 4}, x, y \in S} d_{J (G)} (v_{i} x, v_{j} y)$ 。

现在我们来计算 $W (M)$ ：

对于任意边 $v_{2} x, v_{3} x \in E (G)$ 和 $v_{3} y, v_{4} y \in E (G)$ 其中 $x, y \in S$ ，则 $d_{J (G)} (v_{2} x, v_{3} x) = d_{J (G)} (v_{3} y, v_{4} y) = 2$ 。因此

$W_{11} = \sum_{x \in S} d_{J (G)} (v_{2} x, v_{3} x) + \sum_{y \in S} d_{J (G)} (v_{3} y, v_{4} y) = 2 (n_{1} + n_{2})$ .

对于任意边 $v_{2} x, v_{4} x \in E (G) (x \in S)$ ，则 $d_{J (G)} (v_{2} x, v_{4} x) = 3$ 。因此

$W_{12} = \sum_{x \in S} d_{J (G)} (v_{2} x, v_{4} x) = 3 n_{3}$ .

对于任意边 $v_{i} x, v_{j} y \in E (G) (x, y \in S, i, j \in {2, 3, 4} 且 i \neq j)$ ，则 $d_{J (G)} (v_{i} x, v_{j} y) = 1$ 。因此

$W_{13} = \sum_{\begin{matrix} i, j \in {2, 3, 4}, i \neq j \\ x, y \in S, x \neq y \end{matrix}} d_{J (G)} (v_{i} x, v_{j} y) = d_{2} d_{3} + d_{2} d_{4} + d_{3} d_{4} - (n_{1}^{2} + n_{2}^{2} + n_{3}^{2})$ .

对于任意边 $v_{i} x, v_{i} y \in E (G) (x, y \in S, i \in (2, 3, 4))$ ，则 $d_{J (G)} (v_{i} x, v_{i} y) = 2$ 。因此

$W_{14} = \sum_{i \in {2, 3, 4}, x, y \in S} d_{J (G)} (v_{2} x, v_{4} y) = d_{2}^{2} + d_{3}^{2} + d_{4}^{2} - (d_{2} + d_{3} + d_{4})$ .

综上所述：

$\begin{matrix} W (M) = W_{11} + W_{12} + W_{13} + W_{14} \\ = d_{2}^{2} + d_{3}^{2} + d_{4}^{2} + d_{2} d_{3} + d_{2} d_{4} + d_{3} d_{4} - (m - 4) \\ - (n_{1}^{2} + n_{2}^{2} + n_{3}^{2}) + 2 (n_{1} + n_{2}) + 3 n_{3} \end{matrix}$ .

因此

$\begin{matrix} W (J (G)) = d_{2}^{2} + d_{3}^{2} + d_{4}^{2} + d_{2} d_{3} + d_{2} d_{4} + d_{3} d_{4} + 5 (m - 4) \\ - (n_{1}^{2} + n_{2}^{2} + n_{3}^{2}) + 2 (n_{1} + n_{2}) + 3 n_{3} + 10 \end{matrix}$ .

2.4. 直径等于4

由定理2.1.2知：当 $d i a m (J (G)) = 4$ ，G有三种结构形式 $G_{n}, H_{n}$ 和 $F_{n}$ ，如图2所示。

$V (G_{n}) = {u, v, w, x, y_{1}, \dots, y_{n - 4}}$ , $E (G_{n}) = {u v, u w, w x, x u} \cup {u y_{i} | 1 \leq i \leq n - 4}$ .

$V (H_{n}) = {u, v, w, x, y_{1}, \dots, y_{n - 4}}$ , $E (H_{n}) = {u v, u w, w x, x u, v x} \cup {u y_{i} | 1 \leq i \leq n - 4}$ .

$V (F_{n}) = {u, v, w, x, y_{1}, \dots, y_{n - 4}}$ , $E (F_{n}) = {u v, u w, w x, x u, v x, u w} \cup {u y_{i} | 1 \leq i \leq n - 4}$ .

Figure 2. $G_{n}, H_{n}$ and $F_{n}$

图2. $G_{n}, H_{n}$ 和 $F_{n}$

定理2.4.1 对于一个点数为n的图G，如果 $d i a m (J (G)) = 3$ ，则

$W (J (G)) = {\begin{cases} n^{2} - 3 n + 10, 若 G ≅ G_{n}; \\ n^{2} - 2 n + 11, 若 G ≅ H_{n}; \\ n^{2} + 23, 若 G ≅ F_{n} . \end{cases}$

证明：对于任意图G，如果 $G ≅ G_{n}$ ，则对于任意边，有 $d_{J (G)} (u y_{i}, u y_{j}) = 2$ 。因此

$W_{21} = \sum_{i, j \in {1, 2, \dots, n - 4}} d_{J (G)} (u y_{i}, u y_{j}) = 2 (\begin{matrix} n - 4 \\ 2 \end{matrix}) = n^{2} - 9 n + 20$ .

对于任意边 $u y_{i}, u v, u x \in E (G) (i \in {1, 2, \dots, n - 4})$ ，则 $d_{J (G)} (u y_{i}, u v) = d_{J (G)} (u y_{i}, u x) = 2$ 。因此

$W_{22} = \sum_{i \in {1, 2, \dots, n - 4}} d_{J (G)} (u y_{i}, u v) + \sum_{i \in {1, 2, \dots, n - 4}} d_{J (G)} (u y_{i}, u x) = 2 \times 2 (n - 4) = 4 n - 16$ .

对于任意边 $u y_{i}, w v, w x \in E (G) (i \in {1, 2, \dots, n - 4})$ ，显然 $d_{J (G)} (u y_{i}, w v) = d_{J (G)} (u y_{i}, w x) = 1$ 。因此

$W_{23} = \sum_{i \in {1, 2, \dots, n - 4}} d_{J (G)} (u y_{i}, w v) + \sum_{i \in {1, 2, \dots, n - 4}} d_{J (G)} (u y_{i}, w x) = 2 \times (n - 4) = 2 n - 8$ .

同理， $d_{J (G)} (u x, x w) = d_{J (G)} (u v, v w) = 3$ ， $d_{J (G)} (u x, u v) = 4$ ， $d_{J (G)} (w v, w x) = 2$ ， $d_{J (G)} (w x, u v) = d_{J (G)} (u x, v w) = 1$ 。

综上所述：

$\begin{matrix} W (M) = W_{21} + W_{22} + W_{23} + d_{J (G)} (u x, x w) + d_{J (G)} (u v, v w) + d_{J (G)} (u x, u v) \\ + d_{J (G)} (w v, w x) + d_{J (G)} (w x, u v) + d_{J (G)} (u x, v w) \\ = n^{2} - n + 20 + 4 n - 16 + 2 n - 8 + 2 \times 3 + 4 + 2 + 2 \times 1 \\ = n^{2} - 3 n + 10 \end{matrix}$ .

根据上面的方法我们得到，若 $G ≅ H_{n}$ 或 $G ≅ F_{n}$ ，有

$W (J (G)) = {\begin{cases} n^{2} - 2 n + 11, 若 G ≅ H_{n}; \\ n^{2} + 23, 若 G ≅ F_{n} . \end{cases}$

基金项目

国家自然科学基金青年科学基金(NO. 11801487)。

参考文献

[1]	Dobrynin, A.A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Applications. Acta Applicandae Mathematicae, 66, 211-249. https://doi.org/10.1023/A:1010767517079
[2]	An, X. and Wu, B. (2007) Ham-iltonicity of Complements of Middle Graphs. Discrete Mathematics, 307, 1178-1184. https://doi.org/10.1016/j.disc.2006.07.028
[3]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Appli-cations. American Elsevier, New York, Macmillan, London. https://doi.org/10.1007/978-1-349-03521-2
[4]	Chen, X., Liu, J., Xie, D. and Meng, J. (2016) Edge Connectivity and Super Edge-Connectivity of Jump Graphs. Information and Optimization Sciences, 37, 233-246. https://doi.org/10.1080/02522667.2015.1103062
[5]	Chartrand, G., Hevia, H., Jarrett, E.B. and Schultz, M. (1997) Subgraph Distances in Graphs Defind by Edge Transfers. Discrete Mathematics, 170, 63-79. https://doi.org/10.1016/0012-365X(95)00357-3
[6]	Gutman, I. and Körtvelyesia, T. (1995) Wiener Indices and Molecular Surfaces. Zeitschrift für Naturforschung, 50, 669-671.
[7]	Knor, M., Skrekovski, R. and Tepeh, A. (2015) Mathematical Aspects of Wiener Index. Graphs and Combinatorics, 29, 1403-1416.
[8]	Wu, B. and Meng, J. (2004) Hamiltonian Jump Graphs. Discrete Mathematics, 289, 95-106. https://doi.org/10.1016/j.disc.2004.09.003
[9]	Wu, B. and Guo, X. (2001) Diameters of Jump Graphs and Self-Complementary Jump Graphs. Graph Theory Notes of New York, 40, 31-34.
[10]	Wu, B., Liu, X. and Guo, X. (2008) Super-Connected and Hyper-Connected Jump Graphs. International Journal of Computer Mathematics, 85, 1765-1769. https://doi.org/10.1080/00207160701600069

为你推荐

友情链接