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 $$D £
7.
To find the solution of the problem we use
the irrelevant path method.
It is proved that the known graphs with size $2$D
+1 ($3$£ D £ 4) and $$D
+5 ($5$£ D £ 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 $$D £
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.

Location: http://mech.math.msu.su/~fpm/eng/k01/k014/k01414h.htm

Last modified: April 17, 2002