图运算下的总离心率及多项式

The Total Eccentricity and Polynomial of Some Graph Operations

摘要: 让G表示一个简单连通图，图G的总离心率及多项式分别定义为，，这里是顶点ν在G中的离心率。在本文中，计算了在图运算下图的双覆盖图和拓展双覆盖图以及剖分图的总离心率及多项式，并给出具体的关系表达式和一些界。

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.

文章引用：詹明锦. 图运算下的总离心率及多项式[J]. 应用数学进展, 2015, 4(4): 385-389. http://dx.doi.org/10.12677/AAM.2015.44048

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)资助。

参考文献

[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

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)资助。