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.