FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2001, VOLUME 7, NUMBER 4, PAGES 1203-1225

The largest graphs of diameter 2 and fixed Euler characteristics

S. A. Tishchenko

Abstract

View as HTML     View as gif image    View as LaTeX source

We compute the exact maximum size of a planar graph with diameter $2$ and fixed maximum degree $\Delta\leq 7$. To find the solution of the problem we use the irrelevant path method. It is proved that the known graphs with size $2\Delta+1$ ($3\leq \Delta\leq 4$) and $\Delta+5$ ($5\leq\Delta\leq 7$) are the largest possible ones. This result completes the analysis of the degree--diameter problem for planar graphs of diameter $2$. In the case $\Delta\leq 6$, we found also the largest graphs of diameter $2$ that are embedded into the projective plane and into the torus.

All articles are published in Russian.

Main page Contents of the journal News Search

Location: http://mech.math.msu.su/~fpm/eng/k01/k014/k01414t.htm.
Last modified: April 17, 2002