Unimodal eccentricity in trees. Issue 2 (5th December 2020)

• Record Type: Journal Article
• Authors: Gylfason, Jökull S.; Hilmarsson, Bernhard L.; Tonoyan, Tigran
• Is Part Of: Networks. Volume 78:Issue 2(2021)
• Page Start: 188
• Page End: 194
• Publication Date: 2020-12-05
• Subjects: convex -- eccentricity -- Jordan's theorem -- tree center -- unimodal -- weighted; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22013
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: Jordan's classic theorem states that the center of every tree (the set of minimum eccentricity vertices) forms a complete subgraph. This property, which we refer to as the "Jordan property, " has been established for various definitions of eccentricity, the most popular being the maximum and average distances of a vertex to the others. In this note, we consider unimodal eccentricity functions, such that in every tree, the eccentricity strictly increases along every center‐to‐leaf path (whose second vertex is not in the center). Unimodal eccentricity implies the Jordan property. We prove that every function of distances with appropriate convexity and monotonicity is a unimodal eccentricity function. This covers many functions of distances that have been known to satisfy the Jordan property, and many others for which the Jordan property was not known prior to this work. Most of our results hold for trees with arbitrary positive weights on edges.