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