AAM  >> Vol. 8 No. 4 (April 2019)

作者:  

赵艳华:新疆大学,数学与系统科学学院,新疆 乌鲁木齐

关键词:
变换图Wiener指标Transformation Graph Wiener Index

摘要:

图G的变换图G---的顶点集为V(G)∪E(G),图G---中任意两顶点u,v∈V(G---)只需满足下面任意一个条件便可以连边:1) u,v∈V(G),它们在图G中不相邻,2)u,v∈E(G),它们在图G中不相邻,3) u∈V(G) v∈E(G),它们在图G中不关联。图G的Wiener指标是图G中所有点对的距离之和。在本文中,我们确定了变换图G---是连通图时的Wiener指标。

The transformation graph G--- of a graph G is the graph with vertex set V(G)∪E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: 1) u,v∈V(G) and they are not adjacent in G, 2) u,v∈E(G) and they are not adjacent in G, 3) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. The Wiener index W(G) of G is the sum of the distances between all pairs of vertices in G. In this note, for any graph G, we de-termine the Wiener index of G---, when G--- is connected.

1. 引言

本篇文章中所有的图都为无向的简单图。所用到的符号和术语参考文献 [1] 。设简单图 G 的顶点集为 V ( G ) ,图 G 的边集为 E ( G ) 。对于 V ( G ) 中的任意顶点 v ,我们记 N G ( v ) 为图 G 中所有和顶点 v 相邻的顶点的集合。称 d G ( v ) = | N G ( v ) | 为顶点 v 的度数。

在一个连通图 G 中,用 d G ( u , v ) 表示 G 中任意两个顶点u和v之间的距离(两点之间最短路的长度),图 G 的Wiener指标是指图 G 中所有顶点对的距离之和,即 W ( G ) = u , v V ( G ) d G ( u , v ) 。在不引起歧义的情况下,我们把 d G ( v ) d G ( u , v ) 分别简记为 d ( v ) d ( u , v )

这个概念最初是由Harry Wiener在1947年的文献 [2] 中提到的,之后作为一个重要的拓扑指标应用于化学研究中,用来研究分子的结构。后来Entringer等人在1976年文献 [3] 中首次引入到数学领域,引起许多数学家的兴趣。关于一些Wiener指标的化学应用和数学研究的调查可以参考文献 [4] 以及其中引用的参考资料。

吴和孟在文献 [5] 中给出了全变换图的基本性质。我们可以在文献 [6] [7] [8] 中查阅到变换图的更多结果。

在本文中,我们将根据吴和孟的结果确定连通的变换图 G --- 的Wiener指标。

2. 主要内容

2.1. 预备知识

在文献 [5] 中吴和孟给出了下面的结果。

定理2.1.1: [5] 如果图 G 既不是星图也不是三角形,则 diam ( G ) 3

当图 G 是星图或者是三角形的时候,图 G --- 是不连通的。由定理2.1.1的证明过程可知,当 u , v V ( G ) 时, d ( u , v ) 3 ;当 u , v E ( G ) 时, d ( u , v ) 2 ;当 u V ( G ) , v E ( G ) 时, d ( u , v ) 3 。而且当 diam ( G ) = 3 ,我们有图 G 的结构(如图1所示)。

图1(1)中,在其变换图中距离是3的顶点对为 u , v ;如图1(2)中,在其变换图中距离是3的顶点对为 u , v u , w u , u v u , u w ;如图1(3)中,在其变换图中距离是3的顶点对为 u , v u , u v ;如图1(4)中,在其变换图中距离是3的顶点对为 u , v u , u v v , v u

在本文,我们主要根据上面直径求变换图 G 的Wiener指标。

2.2. 直径小于等于2

当顶点 u 和边 e 关联时,我们记为 m u e = 1 ,当边 e , f 相邻时记为 m e f = 1 。否则,我们分别记为 m u v = 0 m e f = 0

Figure 1. diam ( G ) = 3

图1. diam ( G ) = 3

定理2.2.1:如果图 G 的顶点的阶数为 n ,边的阶数为 m ,且 diam ( G ) 2 ,则

W ( G ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n .

证明:记 u , v 为图 G 中任意两个顶点, e , f 为图 G 中任意两条边, V ( G ) = { u 1 , u 2 , u m + n } 。在图 G 相邻边的个数为 v V ( G ) ( d G ( v ) 2 ) ,又因为 diam ( G ) 2 ,所以对于任意的点 u 1 , u 2 V ( G ) u 1 u 2 之间的距离为1或2。因此,由Wiener指标的定义可知:

W ( G ) = u , v d G ( u , v ) + u , e d G ( u , e ) + e , f d G ( e , f ) = ( u v E ( G ) d G ( u , v ) + u v E ( G ) d G ( u , v ) ) + ( m u e = 0 d G ( u , e ) + m u e = 1 d G ( u , e ) ) + ( m e f = 0 d G ( e , f ) + m e f = 1 d G ( e , f ) ) = ( ( n 2 ) m + 2 m ) + ( m n 2 m + 4 m ) + ( ( m 2 ) v V ( G ) ( d G ( v ) 2 ) + 2 v V ( G ) ( d G ( v ) 2 ) ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n .

2.3. 直径等于3

定理2.3.1:如果图 G 的边数为 m ,顶点数为 n ,当 diam ( G ) = 3 时,则具有图1四类图中的某一种结构,且对应的Wiener指标分别为

1) W ( G ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 1

2) W ( G ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 4

3) W ( G ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 2

4) W ( G ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 3

证明:首先由定理2.1.1的证明可以知道,直径可以达到3的变换图 G 的原图 G 的结构只有图1中四种结构。下面分别给出它们的Wiener指标。

对于图1(1),容易看出图 G 中距离是3的点对只有 u , v 。从而

W ( G ) = u , v d G ( u , v ) + u , e d G ( u , e ) + e , f d G ( e , f ) = ( u v E ( G ) d G ( u , v ) + u v E ( G ) d G ( u , v ) ) + ( m u e = 0 d G ( u , e ) + m u e = 1 d G ( u , e ) ) + ( m e f = 0 d G ( e , f ) + m e f = 1 d G ( e , f ) ) = ( ( n 2 ) m + 2 ( m 1 ) + 3 ) + ( m n 2 m + 4 m ) + ( ( m 2 ) v V ( G ) ( d G ( v ) 2 ) + 2 v V ( G ) ( d G ( v ) 2 ) ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 1.

对于图1(2),容易看出图 G 中距离是3的顶点对为 u , v u , w u , u v u , u w 。从而

W ( G ) = u , v d G ( u , v ) + u , e d G ( u , e ) + e , f d G ( e , f ) = ( u v E ( G ) d G ( u , v ) + u v E ( G ) d G ( u , v ) ) + ( m u e = 0 d G ( u , e ) + m u e = 1 d G ( u , e ) ) + ( m e f = 0 d G ( e , f ) + m e f = 1 d G ( e , f ) ) = ( ( n 2 ) m + 2 ( m 2 ) + 3 × 2 ) + ( m n 2 m + 2 ( 2 m 2 ) + 3 × 2 ) + ( ( m 2 ) v V ( G ) ( d G ( v ) 2 ) + 2 v V ( G ) ( d G ( v ) 2 ) ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 4.

对于图1(3),容易看出图 G 中距离是3的顶点对为 u , v u , u v 。从而

W ( G ) = u , v d G ( u , v ) + u , e d G ( u , e ) + e , f d G ( e , f ) = ( u v E ( G ) d G ( u , v ) + u v E ( G ) d G ( u , v ) ) + ( m u e = 0 d G ( u , e ) + m u e = 1 d G ( u , e ) ) + ( m e f = 0 d G ( e , f ) + m e f = 1 d G ( e , f ) ) = ( ( n 2 ) m + 2 ( m 1 ) + 3 ) + ( m n 2 m + 2 ( 2 m 1 ) + 3 ) + ( ( m 2 ) v V ( G ) ( d G ( v ) 2 ) + 2 v V ( G ) ( d G ( v ) 2 ) ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 2.

对于图1(4),容易看出图 G 中距离是3的顶点对为 u , v u , u v v , v u 。从而

W ( G ) = u , v d G ( u , v ) + u , e d G ( u , e ) + e , f d G ( e , f ) = ( u v E ( G ) d G ( u , v ) + u v E ( G ) d G ( u , v ) ) + ( m u e = 0 d G ( u , e ) + m u e = 1 d G ( u , e ) ) + ( m e f = 0 d G ( e , f ) + m e f = 1 d G ( e , f ) ) = ( ( n 2 ) m + 2 ( m 1 ) + 3 ) + ( m n 2 m + 2 ( 2 m 2 ) + 3 × 2 ) + ( ( m 2 ) v V ( G ) ( d G ( v ) 2 ) + 2 v V ( G ) ( d G ( v ) 2 ) ) = 1 2 ( m 2 + n 2 + v V ( G ) d G 2 ( v ) ) + m n + 3 2 m 1 2 n + 3.

文章引用:
赵艳华. 变换图G---的Wiener指标[J]. 应用数学进展, 2019, 8(4): 703-707. https://doi.org/10.12677/AAM.2019.84080

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. American Elsevier, New York, Macmillan, London.
[2] Wiener, H. (1947) Structural Determination of Paraffin Boiling Point. 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] Dobrynin, A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Applications. Acta Applicandae Mathematica, 66, 211-249.
https://doi.org/10.1023/A:1010767517079
[5] Wu, B. and Meng, J. (2001) Basic Properties of Total Transformation Graphs. Journal of Mathematical Study, 34, 109-116.
[6] Wu, B., Zhang, L. and Zhang, Z. (2005) The Transformation Graph Gxyz When xyz = −++. Discrete Mathematics, 296, 263-270.
[7] Chen, J. (2006) Super Edge-Connectivity of Two Classes of Transformation Graphs. Doctoral Thesis, Xinjiang University, Urumchi.
[8] Xu, L. and Wu, B. (2008) Transformation Graph . Discrete Mathematics, 308, 5144-5148.