The k-eccentricity evaluated at a point x of a graph G is the sum of the (weighted) distances from x to the k vertices farthest from it. The k-centrum is the set of vertices for which the k-eccentricity is a minimum. The concept of k-centrum includes, as a particular case, that of center and that of centroid (or median) of a graph. The absolute k-centrum is the set of points (not necessarily vertices) for which the k-eccentricity is a minimum. In this paper it will be proven that, for a weighted tree, both deterministic and probabilistic, the k-eccentricity is a convex function and that the absolute k-centrum is a connected set and is contained in an elementary path. Hints will be given for the construction of an algorithm to find the k-centrum and the absolute k-centrum.

K-eccentricity and absolute k-centrum of a probabilistic Tree

ANDREATTA, GIOVANNI;
1985

Abstract

The k-eccentricity evaluated at a point x of a graph G is the sum of the (weighted) distances from x to the k vertices farthest from it. The k-centrum is the set of vertices for which the k-eccentricity is a minimum. The concept of k-centrum includes, as a particular case, that of center and that of centroid (or median) of a graph. The absolute k-centrum is the set of points (not necessarily vertices) for which the k-eccentricity is a minimum. In this paper it will be proven that, for a weighted tree, both deterministic and probabilistic, the k-eccentricity is a convex function and that the absolute k-centrum is a connected set and is contained in an elementary path. Hints will be given for the construction of an algorithm to find the k-centrum and the absolute k-centrum.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/111161
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 18
  • OpenAlex ND
social impact