zbMATH — the first resource for mathematics

Graphs related to diameter and center. (English) Zbl 0922.05023
Summary: A graph is said to be an \(L\)-graph if all its paths of diametral length contain a central vertex of \(G\). Using an earlier result we show that any graph can be embedded to an \(L\)-graph of radius \(a\) and diameter \(b\), where \(a \leq b \leq 2a\). We show that the known bounds of the number of edges and the maximum degree of the graphs of diameter \(d \leq 2\) are sharp for \(L\)-graphs, too. Then we estimate the minimum degree of \(L\)-graphs. Finally we estimate the number of central vertices in \(L\)-graphs; all bounds are best possible.
05C12 Distance in graphs
05C35 Extremal problems in graph theory
Full Text: EMIS EuDML