FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2001, VOLUME 7, NUMBER 4, PAGES 1203-1225
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