Article collection "Mathematical Problems of Cybernetics" №3, Moscow, 1991

Authors:Yushmanov S.V., Chepoi V.D.

A general method for studying metric characteristics of graphs related with eccentricity

Abstract:

The notions of diameter, radius and center for a graph are not only of theoretical interest, but also arise naturally in applications. The lack of general methods for estimating the metric characteristics of a graph implies the necessity to create special methods for particular classes of graphs that are as a rule inapplicable outside the said class. Previously the authors have introduced a metric family of graphs, dubbed the α_{i}-metric. Many metric characteristics and properties of graphs were shown to be described in terms of the α_{i}-metric This allows to reduce the problem of computing them to the problem of finding the minimal value of i, for which the graph possesses an α_{i}-metric. The aim of the present work is to demonstrate the fruitfulness of this approach. We present the basic definitions and the characteristics of graphs with an α_{0} and α_{i}-metrics. In particular we show that Ptolemaic graphs have an α_{0} -metric and the chordal graphs have an α_{i}-metric. We also prove that finite graphs with an α_{i}-metric satisfy the estimate d(G)≥2r(G)-i-1 while the distance hereditary graphs and some important subclasses of the chordal graph class also satisfy the estimate d(G)≥2r(G)-i. We also investigate some properties of graph centers for graphs with an α_{i}-metric having i≤2.

Keywords:

graph theory, metric characteristics of a graph, eccentricity, α_{i}-metric