Advances in Applied Mathematics
Vol.04 No.04(2015), Article ID:16449,5
pages
10.12677/AAM.2015.44048
The Total Eccentricity and Polynomial of Some Graph Operations
Mingjin Zhan
Department of Mathematics, Qinghai Normal University, Xining
Received: Nov. 6th, 2015; accepted: Nov. 22nd, 2015; published: Nov. 30th, 2015
Copyright © 2015 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/
ABSTRACT
Let G be a simple connected graph. The total eccentricity
and total eccentricity polynomial
of a graph G are defined as
and
, where
denotes the eccentricity of vertex
in G. In this paper, the total eccentricity and total eccentricity polynomial of double cover graph and extended double cover graph and subdivision graph of a given graph under the graph operations are computed and the exact expressions and some bounds are given.
Keywords:Total Eccentricity, Total Eccentricity Polynomial, Graph Operations
图运算下的总离心率及多项式
詹明锦
青海师范大学数学系，青海 西宁
收稿日期：2015年11月6日；录用日期：2015年11月22日；发布日期：2015年11月30日
摘 要
让
表示一个简单连通图，图
的总离心率
及多项式
分别定义为
，
，这里
是顶点
在
中的离心率。在本文中，计算了在图运算下图的双覆盖图和拓展双覆盖图以及剖分图的总离心率及多项式，并给出具体的关系表达式和一些界。
关键词 :总离心率，总离心多项式，图运算
1. 引言
设
是一个简单连通图，顶点集为
，边集为
。对两个点
，它们的距离的定义为它们之间的最短路径的长度，记为
。顶点
的离心率
是
到其它点的距离的最大值。用
表示顶点
的度。若
，则称
为好连接点。用
表示图
中好连接点的个数。
一个最早研究基于距离的分子结构描述符是Winner指数[1] ，这一拓扑指标在数学文献中已经被广泛研究，另一个关于距离的研究指标是离心连通指标，是Sharma，Goswami和Madan [2] 引入的，离心连通
指标用
表示，定义为
，关于与这方面研究相关的文章可以参考文献[3] [4] ，总离心指标是基于离心连通指标而提出的另一种研究距离的指标，用
表示，定义为：
，多项式定义
，其中
，本文主要考虑它的数学性质。
对于连通图
，用
表示
的顶点集，其双覆图
定义如下：与
对应，在
中有两个顶点集
和
，对每条边
，有
，
，
，
。
拓展双覆图
：同样与
对应，在
中也有两个顶点集
和
，对
，有
，
，
，
。
剖分图
是在图
的每一条边上都插入一个新的顶点而得到的图，也是等价于
的每一条边都被换成一个长度为2的路，剖分的图
的双覆盖图用
表示，拓展双覆盖图用
表示。
2. 主要结果
定理1. 如果
是具有好连接点的连通图，那么
，
。
证明：因为图
含有好连接点，由离心率的定义得，图
中的任意点的离心率要么为1，要么为2，从而可把
中的顶点分成两类。用
表示顶点离心率为1的点的集合，用
表示顶点离心率为2的点的集合，则：
定理2. 设
是一个连通图，则
，
。
证明：由双图覆盖图的定义可得：
，当
，
，当
，
[5] ，则
推论1. 如果一个连通图G不具有连接好点，则
，
。
证明：因为图G无好连接点，所以
。由定理1可得
，
，成立。
推论2. 如果连通图G具有好连接点，则
，
。
证明：由定理1和定理2可得。
定理3. 设G是双覆盖连通图，
是它的拓展双覆盖图，则
，
。
证明：由拓展双覆盖图的定义可得：
(
) [5] ，所以
，
。
推论3. 如果连通图G具有好连接点，则
，
。
证明：由定理1和定理3可得。
推论4. 连通图G的双图覆盖图
与双覆盖图
的关系为：
，
。
证明：由定理2和定理3可得。
引理[6] ：设G是一个连通图，则有：
1) 对任意
，有
，
2) 对任意
，有
。
定理4. 设G是一个连通图，则
的总离心率及多项式满足：
，
证明：由总离心率及多项式定义和引理[6] 得：
，
。
当
时，有
，所以
当
时，有
，所以
综上可得，对任意
有：
而
，
推论6. 设
(
)是一个连通图，则
，
证明：由定理2和定理4可得。
推论7. 设G是一个连通图，则
，
证明：由定理3和定理4可得。
致谢
感谢国家自然基金项目(NO.61164005)资助。
文章引用
詹明锦. 图运算下的总离心率及多项式
The Total Eccentricity and Polynomial of Some Graph Operations[J]. 应用数学进展, 2015, 04(04): 385-389. http://dx.doi.org/10.12677/AAM.2015.44048
参考文献 (References)
- 1. Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20. http://dx.doi.org/10.1021/ja01193a005
- 2. Sharma, V., Gosami, R. and Madan, A.K. (1997) Eccentric Con-nectivity Index: A Novel Highly Discriminating Topological Descriptor for Structure-Property and Structure-Activity Studies. Journal of Chemical Information and Computer Science, 37, 273-282. http://dx.doi.org/10.1021/ci960049h
- 3. Morgan, M.J., Mukembi, S. and Swart, H.C. (2010) On the Eccentric Con-nectivity Index of a Graph. Discrete Mathematics, 311, 1229-1234.
- 4. Ilić, A. and Gutman, I. (2011) Eccentric Connectivity Index of Chemical Trees. Match Communications in Mathematical and in Computer Chemistry, 65, 731-744.
- 5. Bindusree, A.R., Lokesha, V. and P.S.R. (2015) Eccentric Connectivity Index and Polynomial of Some Graph Operations. British Journal of Mathematics & Computer Science, 6, 457-463.
- 6. Yarahmadi, Z., Moradi, S. and Došlić, T. (2014) Eccentric Connectivity Index of Graph with Subdivided Edges. Electronic Notes in Discrete Mathematics, 45, 167-176. http://dx.doi.org/10.1016/j.endm.2013.11.031