Eccentricity sums in trees

详细信息    查看全文

• 作者：Heather Smith^a ; ^{smithhc5@math.sc.edu" class="auth_mail" title="E-mail the corresponding author} ; Lá ; szló ; Szé ; kely^a ; ^{szekely@math.sc.edu" class="auth_mail" title="E-mail the corresponding author} ; Hua Wang^b ; ^{hwang@georgiasouthern.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Eccentricity ; Extremal problems ; Degree sequence ; Greedy caterpillar ; Greedy tree ; Level-greedy tree
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 July 2016
• 年：2016
• 卷：207
• 期：Complete
• 页码：120-131
• 全文大小：485 K

文摘

The eccentricity of a vertex, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si33.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=e450fce1780e19ba572ada971e4df31a" title="Click to view the MathML source">ecc_T(v)=max_u∈Td_T(v,u)class="mathContainer hidden">class="mathCode">${ecc}_T\left(v\right)={max}_{u\in T}{d}_T(v,u)$, was one of the first, distance-based, tree invariants studied. The total eccentricity of a tree, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si34.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=878fba98ff83d1c84a96db785e4eeb84" title="Click to view the MathML source">Ecc(T)class="mathContainer hidden">class="mathCode">$Ecc\left(T\right)$, is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si35.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=1a79b0edb2df8cf9d72941a59b895133" title="Click to view the MathML source">Ecc(T)/ecc_T(u)class="mathContainer hidden">class="mathCode">$Ecc\left(T\right)/{ecc}_T\left(u\right)$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si36.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=7ab190cf3344595ba4813ae151cbaeb5" title="Click to view the MathML source">Ecc(T)/ecc_T(v)class="mathContainer hidden">class="mathCode">$Ecc\left(T\right)/{ecc}_T\left(v\right)$, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si37.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=42ab907bee637e9146c813629ef14c9d" title="Click to view the MathML source">ecc_T(u)/ecc_T(v)class="mathContainer hidden">class="mathCode">${ecc}_T\left(u\right)/{ecc}_T\left(v\right)$, and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si38.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=a7ea0913984739cc79fc93583d67bcd5" title="Click to view the MathML source">ecc_T(u)/ecc_T(w)class="mathContainer hidden">class="mathCode">${ecc}_T\left(u\right)/{ecc}_T\left(w\right)$ where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si39.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=5833f865e4d3def0d85a717a7e02a1c4" title="Click to view the MathML source">u,wclass="mathContainer hidden">class="mathCode">$u,w$ are leaves of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si9.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=afc68669cdea886d5237977ea7022eaa" title="Click to view the MathML source">Tclass="mathContainer hidden">class="mathCode">$T$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si10.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=9e519ba92918ec913df170b6a5af46cc" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$ is in the center of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16300646&_mathId=si9.gif&_user=111111111&_pii=S0166218X16300646&_rdoc=1&_issn=0166218X&md5=afc68669cdea886d5237977ea7022eaa" title="Click to view the MathML source">Tclass="mathContainer hidden">class="mathCode">$T$. In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence.