The normality and sum of normalities of trees

DOI10.1016/J.DISC.2019.111635zbMATH Open1429.05037arXiv1908.11802OpenAlexW2969301449WikidataQ127334885 ScholiaQ127334885MaRDI QIDQ2279281FDOQ2279281

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

Publication date: 12 December 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

treenormalityeccentricityextremal treemiddle part

Mathematics Subject Classification ID

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

Cites Work

• Upper bounds on the average eccentricity
• Eccentricity sums in trees
• A generalized algorithm for centrality problems on trees
• On two eccentricity-based topological indices of graphs
• Peripheral Wiener index of trees and related questions
• Title not available (Why is that?)

Cited In (5)

• Some extremal problems on the distance involving peripheral vertices of trees with given matching number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing new families of transmission irregular graphs
• Variations of the eccentricity and their properties in trees

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)