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