Eccentricity sums in trees

Heather Smith; László Székely; Hua Wang

doi:10.1016/j.dam.2016.02.013

Eccentricity sums in trees

Heather Smith, László Székely, Hua Wang

Mathematical Sciences

University of South Carolina

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

The eccentricity of a vertex, _eccT(v)=_maxu∈T_dT(v,u), was one of the first, distance-based, tree invariants studied. The total eccentricity of a tree, Ecc(T), is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios Ecc(T)/_eccT(u), Ecc(T)/_eccT(v), _eccT(u)/_eccT(v), and _eccT(u)/_eccT(w) where u,w are leaves of T and v is in the center of T. In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence.

Original language	English
Pages (from-to)	120-131
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	207
DOIs	https://doi.org/10.1016/j.dam.2016.02.013
State	Published - Jul 10 2016

Scopus Subject Areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Degree sequence
Eccentricity
Extremal problems
Greedy caterpillar
Greedy tree
Level-greedy tree

Access to Document

10.1016/j.dam.2016.02.013

Cite this

@article{a4770aa82d38405d803f82deea6971f4,

title = "Eccentricity sums in trees",

abstract = "The eccentricity of a vertex, eccT(v)=maxu∈TdT(v,u), was one of the first, distance-based, tree invariants studied. The total eccentricity of a tree, Ecc(T), is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios Ecc(T)/eccT(u), Ecc(T)/eccT(v), eccT(u)/eccT(v), and eccT(u)/eccT(w) where u,w are leaves of T and v is in the center of T. In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence.",

keywords = "Degree sequence, Eccentricity, Extremal problems, Greedy caterpillar, Greedy tree, Level-greedy tree",

author = "Heather Smith and L{\'a}szl{\'o} Sz{\'e}kely and Hua Wang",

year = "2016",

month = jul,

day = "10",

doi = "10.1016/j.dam.2016.02.013",

language = "English",

volume = "207",

pages = "120--131",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Eccentricity sums in trees

AU - Smith, Heather

AU - Székely, László

AU - Wang, Hua

PY - 2016/7/10

Y1 - 2016/7/10

N2 - The eccentricity of a vertex, eccT(v)=maxu∈TdT(v,u), was one of the first, distance-based, tree invariants studied. The total eccentricity of a tree, Ecc(T), is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios Ecc(T)/eccT(u), Ecc(T)/eccT(v), eccT(u)/eccT(v), and eccT(u)/eccT(w) where u,w are leaves of T and v is in the center of T. In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence.

AB - The eccentricity of a vertex, eccT(v)=maxu∈TdT(v,u), was one of the first, distance-based, tree invariants studied. The total eccentricity of a tree, Ecc(T), is the sum of the eccentricities of its vertices. We determine extremal values and characterize extremal tree structures for the ratios Ecc(T)/eccT(u), Ecc(T)/eccT(v), eccT(u)/eccT(v), and eccT(u)/eccT(w) where u,w are leaves of T and v is in the center of T. In addition, we determine the tree structures that minimize and maximize total eccentricity among trees with a given degree sequence.

KW - Degree sequence

KW - Eccentricity

KW - Extremal problems

KW - Greedy caterpillar

KW - Greedy tree

KW - Level-greedy tree

UR - http://www.scopus.com/inward/record.url?scp=84960145660&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.02.013

DO - 10.1016/j.dam.2016.02.013

M3 - Article

SN - 0166-218X

VL - 207

SP - 120

EP - 131

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Eccentricity sums in trees

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this