KIAM Main page Web Library  •  Publication Searh  Русский 

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
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.
graph theory, metric characteristics of a graph, eccentricity, αi-metric
Publication language: russian,  pages: 16 (p. 217-232)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Yushmanov Sergei Vladimirovich
  • Chepoi Viktor Dmitrievich