ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 66, 1 (1997)
pp. 21-32

GRAPHS RELATED TO DIAMETER AND CENTER
F. GLIVIAK and P. KYS

Abstract. 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\le b\le 2a$. We show that the known bounds of the number of edges and the maximum degree of the graphs of diameter $d\ge 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.

AMS subject classification.
Keywords.

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc