×

The normality and sum of normalities of trees. (English) Zbl 1429.05037

Summary: 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.

MSC:

05C05 Trees
05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chen, Y.; Wang, H.; Zhang, X.-D., Peripheral wiener index of trees and related questions, Discrete Appl. Math., 251, 135-145 (2018) · Zbl 1401.05090
[2] Dankelmann, P.; Mukwembi, S., Upper bounds on the average eccentricity, Discrete Appl. Math., 167, 72-79 (2014) · Zbl 1284.05194
[3] Hedetniemi, S. M.; Cockayne, E. J., Linear algorithms for finding the Jordan center and path center of a tree, Trans. Sci., 15, 98-114 (1981)
[4] Rosenthal, A.; Pino, J., A generalized algorithm for centrality problems on trees, J. Assoc. Comput. Mach., 36, 349-361 (1989) · Zbl 0674.90097
[5] Smith, H.; Székely, L. A.; Wang, H., Eccentricity sums in trees, Discrete Appl. Math., 207, 120-131 (2016) · Zbl 1337.05021
[6] Xu, K.; Alizadeh, Y.; Das, K. C., On two eccentricity-based topological indices of graphs, Discrete Appl. Math., 233, 240-251 (2017) · Zbl 1372.05119
[7] Jordan, C., Sur les assemblages de lignes, J. Reine Angew. Math., 70, 185-190 (1869) · JFM 02.0344.01
[8] Ádám, A., The centrality of vertices in trees, Stud. Sci. Math. Hung., 9, 285-303 (1974) · Zbl 0319.05101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.