Advances in Applied Mathematics
Vol.06 No.04(2017), Article ID:21398,4
pages
10.12677/AAM.2017.64060
On the Maximal Eccentric Distance Sum of Tree
Xiaofei Wu, Xuegang Chen
Department of Mathematics, North China Electric Power University, Beijing
Received: Jun. 24th, 2017; accepted: Jul. 15th, 2017; published: Jul. 18th, 2017
ABSTRACT
Let be a connected graph. The eccentric distance sum of graph
is defined as
, where
is the eccentricity of the vertex
and
is the sum of all distances from the vertex
. In this paper, we characterize the tree with domination number
and the maximal eccentric distance sum. Some known results have been extended.
Keywords:Tree, Eccentricity, The Eccentric Distance Sum
树的最大离心距离和
吴晓菲,陈学刚
华北电力大学数理学院,北京
收稿日期:2017年6月24日;录用日期:2017年7月15日;发布日期:2017年7月18日
摘 要
设图是一个简单连通图,图
的离心距离和定义为
,其中
表示顶点
的离心率,
表示在图
中顶点
到其它所有顶点的距离和。本文刻画了控制数为
且具有最大离心距离和的树的结构。该结论是若干已有成果的推广。
关键词 :树,离心率,离心距离和
Copyright © 2017 by authors 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的点被称为叶点。与叶点相邻的顶点称为支撑点。令
和
分别表示图
的叶点和支撑点的集合。若
且
,则称
是
的一条非悬挂边。设
,
是指在去掉边
所得到的子图。
是指删去图
中的顶点
以及所有和
相关联的边而得到的子图。
指的是不大于
的最大整数,
为不小于
的最小整数。
2. 引理
引理2.1 [1] .设是树
的一条最长路,且它的端点满足
,
,现构造一个新的树
(如图1),令
,则有
。
树是通过在路
的两个顶点
和
上分别粘贴上
个叶点和
个叶点得到的
阶树。
引理2.2 [1] .。
设是一个
阶树,
是
的一条非悬挂边,设
且
,将
中顶点
与
中的顶点
粘在一起,并在顶点
上粘贴一个叶子,得到一个新树
,则称
是对
中的边
做了一次边替换变换得到的。
设是一个
阶树,
是
的一条悬挂边,满足
,设边
,令
。则称
是
对边
的逆边替换变换得到的。
Figure 1. Tree and
图1. 树和
引理2.3 [2] . 设是一个
阶树,
是一条非悬挂边,
是由
对边
做边替换变换而得到的,那么就有
。
3. 主要结论
令表示控制数为
的
阶树组成的集合。
引理3.1 [1] . 在中,树
有最大的离心距离和。
引理3.2 [3] . 在中,树
有最大的离心距离和。
引理3.3 [4] . 在中,树
有最大的离心距离和。
定理1. 在的
阶树中,
有最大的离心距离和。
证明:当,
,
时,分别由引理3.1,引理3.2和引理3.3知,结论成立。
当时,对任意的
阶树
,设树中最长的路为
,且设
。若从顶点
到顶点
中存在度数大于等于3的顶点,则令第一个度大于等于3的点为
,即
.
现构造新的树
则由引理2.1得。然后再从
中找出最长的路
,按照上述方法构造新的树
,则由引理2.1得
。一直进行下去,直到得到新树,满足对任意非叶点和非支撑点均为二度点。不妨设两个支撑点分别与
个叶点相邻,该新树记为
,其中
。不妨假设
。若
,则由引理2得,
即有最大的离心距离和。
当树的控制数为
,易得
。当
或
时,设顶点
是与
相邻的叶点,对边
及点
用逆边替换变换得到
,则
。由引理2.3得,
。因此
。
综上所述,在所有顶点数为且控制数为
的树中,
的离心距离和最大,即定理1成立。
致谢
本论文是在陈老师的悉心指导下完成的。老师渊博的专业知识,严谨的治学态度和精益求精的工作作风都对我影响深远。不仅使我树立了远大的学术目标、掌握了基本的研究方法,还使我明白了许多待人接物与人处事的道理。本论文从选题到完成,每一步都是在陈老师的指导下完成,倾注了老师大量的心血。在此,谨向陈老师表示衷心的感谢!
文章引用
吴晓菲,陈学刚. 树的最大离心距离和
On the Maximal Eccentric Distance Sum of Tree[J]. 应用数学进展, 2017, 06(04): 504-507. http://dx.doi.org/10.12677/AAM.2017.64060
参考文献 (References)
- 1. Geng, X.Y., Li, S.C. and Zhang, M. (2013) Extremal Values of the Eccentric Distance Sum of Trees. Discrete Applied Mathematics, 161, 2427-2439. https://doi.org/10.1016/j.dam.2013.05.023
- 2. Hua, H.B., Xu, K.X. and Shu, W.N. (2011) A Short and Unified Proof of Yu et al’s Two Results on the Eccentric Distance Sum. Journal of Mathematical Analysis and Applications, 382, 364-366. https://doi.org/10.1016/j.jmaa.2011.04.054
- 3. Miao, L.Y., Cao, Q.Q. and Cui, N. (2015) On the Extremal Values of the Eccentric Distance Sum of Trees. Discrete Applied Mathematics, 186, 199-206. https://doi.org/10.1016/j.dam.2015.01.042
- 4. 朱晓颖, 逄世友. 控制数给定的树的最大离心距离和[J]. 山东大学学报(理学版), 2017, 52(2): 30-36.