Advances in Applied Mathematics
Vol.
08
No.
04
(
2019
), Article ID:
29894
,
5
pages
10.12677/AAM.2019.84080
Wiener Index of Transformation Graph G---
Yanhua Zhao
College of Mathematics and System Science, Xinjiang University, Urumqi Xinjiang
Received: Apr. 3rd, 2019; accepted: Apr. 18th, 2019; published: Apr. 25th, 2019
ABSTRACT
The transformation graph G--- of a graph G is the graph with vertex set , in which two vertices u and v are joined by an edge if one of the following conditions holds: 1) and they are not adjacent in G, 2) and they are not adjacent in G, 3) one of u and v is in while the other is in , and they are not incident in G. The Wiener index of G is the sum of the distances between all pairs of vertices in G. In this note, for any graph G, we determine the Wiener index of G---, when G--- is connected.
Keywords:Transformation Graph, Wiener Index
变换图G---的Wiener指标
赵艳华
新疆大学,数学与系统科学学院,新疆 乌鲁木齐
收稿日期:2019年4月3日;录用日期:2019年4月18日;发布日期:2019年4月25日
摘 要
图G的变换图G---的顶点集为 ,图G---中任意两顶点 只需满足下面任意一个条件便可以连边:1) ,它们在图G中不相邻,2) ,它们在图G中不相邻,3) , ,它们在图G中不关联。图G的Wiener指标是图G中所有点对的距离之和。在本文中,我们确定了变换图G---是连通图时的Wiener指标。
关键词 :变换图,Wiener指标
Copyright © 2019 by author and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
1. 引言
本篇文章中所有的图都为无向的简单图。所用到的符号和术语参考文献 [1] 。设简单图 的顶点集为 ,图 的边集为 。对于 中的任意顶点 ,我们记 为图 中所有和顶点 相邻的顶点的集合。称 为顶点 的度数。
在一个连通图 中,用 表示 中任意两个顶点u和v之间的距离(两点之间最短路的长度),图 的Wiener指标是指图 中所有顶点对的距离之和,即 。在不引起歧义的情况下,我们把 , 分别简记为 , 。
这个概念最初是由Harry Wiener在1947年的文献 [2] 中提到的,之后作为一个重要的拓扑指标应用于化学研究中,用来研究分子的结构。后来Entringer等人在1976年文献 [3] 中首次引入到数学领域,引起许多数学家的兴趣。关于一些Wiener指标的化学应用和数学研究的调查可以参考文献 [4] 以及其中引用的参考资料。
吴和孟在文献 [5] 中给出了全变换图的基本性质。我们可以在文献 [6] [7] [8] 中查阅到变换图的更多结果。
在本文中,我们将根据吴和孟的结果确定连通的变换图 的Wiener指标。
2. 主要内容
2.1. 预备知识
在文献 [5] 中吴和孟给出了下面的结果。
定理2.1.1: [5] 如果图 既不是星图也不是三角形,则 。
当图 是星图或者是三角形的时候,图 是不连通的。由定理2.1.1的证明过程可知,当 时, ;当 时, ;当 时, 。而且当 ,我们有图 的结构(如图1所示)。
如图1(1)中,在其变换图中距离是3的顶点对为 ;如图1(2)中,在其变换图中距离是3的顶点对为 、 、 及 ;如图1(3)中,在其变换图中距离是3的顶点对为 、 ;如图1(4)中,在其变换图中距离是3的顶点对为 、 及 。
在本文,我们主要根据上面直径求变换图 的Wiener指标。
2.2. 直径小于等于2
当顶点 和边 关联时,我们记为 ,当边 相邻时记为 。否则,我们分别记为 , 。
图1.
定理2.2.1:如果图 的顶点的阶数为 ,边的阶数为 ,且 ,则
证明:记 为图 中任意两个顶点, 为图 中任意两条边, 。在图 相邻边的个数为 ,又因为 ,所以对于任意的点 , 和 之间的距离为1或2。因此,由Wiener指标的定义可知:
2.3. 直径等于3
定理2.3.1:如果图 的边数为 ,顶点数为 ,当 时,则具有图1四类图中的某一种结构,且对应的Wiener指标分别为
1)
2)
3)
4)
证明:首先由定理2.1.1的证明可以知道,直径可以达到3的变换图 的原图 的结构只有图1中四种结构。下面分别给出它们的Wiener指标。
对于图1(1),容易看出图 中距离是3的点对只有 。从而
对于图1(2),容易看出图 中距离是3的顶点对为 ; ; 及 。从而
对于图1(3),容易看出图 中距离是3的顶点对为 和 。从而
对于图1(4),容易看出图 中距离是3的顶点对为 ; 及 。从而
文章引用
赵艳华. 变换图G---的Wiener指标
Wiener Index of Transformation Graph G---[J]. 应用数学进展, 2019, 08(04): 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.