The normality and sum of normalities of trees

DOI10.1016/J.DISC.2019.111635MaRDI QIDQ2279281zbMATH OpenOpenAlexWikidataFDO

Authors Hua Wang, Ya-Hong Chen, Xiao-Dong Zhang

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11802

zbMATH Keywords

treenormalityeccentricityextremal treemiddle part

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Abstract: The eccentricity of a vertex $v$ in a graph $G$ is the maximum distance from $v$ to any other vertex. The vertices whose eccentricity are equal to the diameter (the maximum eccentricity) of $G$ are called peripheral vertices. In trees the eccentricity at $v$ can always be achieved by the distance from $v$ to a peripheral vertex. From this observation we are motivated to introduce normality of a vertex $v$ as the minimum distance from $v$ to any peripheral vertex. We consider the properties of the normality as well as the middle part of a tree with respect to this concept. Various related observations are discussed and compared with those related to the eccentricity. Then, analogous to the sum of eccentricities we consider the sum of normalities. After briefly discussing the extremal problems in general graphs we focus on trees and trees under various constraints. As opposed to the path and star in numerous extremal problems, we present several interesting and unexpected extremal structures. Lastly we consider the difference between eccentricity and normality, and the sum of these differences. We also introduce some unsolved problems in the context.

Recommendations

• Some extremal problems on the distance involving peripheral vertices of trees with given matching number
• Eccentric graphs
• Eccentricity sums in trees
• Variations of the eccentricity and their properties in trees
• On the eccentric subtree number in trees

Cites work

• scientific article; zbMATH DE number 3499785 (Why is no real title available?)
• A generalized algorithm for centrality problems on trees
• Eccentricity sums in trees
• On two eccentricity-based topological indices of graphs
• Peripheral Wiener index of trees and related questions
• Upper bounds on the average eccentricity

Cited in

(5)

• scientific article; zbMATH DE number 4183432 (Why is no real title available?)
• Some extremal problems on the distance involving peripheral vertices of trees with given matching number
• Variations of the eccentricity and their properties in trees
• Constructing new families of transmission irregular graphs
• scientific article; zbMATH DE number 5912242 (Why is no real title available?)

This page was built for publication: The normality and sum of normalities of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279281)