FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2001, VOLUME 7, NUMBER 1, PAGES 159-171

Maximum size of a planar graph ($$D=3, $D=3$)

S. A. Tishchenko

Abstract

View as HTML     View as gif image    View as LaTeX source

The problem of maximum size of a graph of diameter $3$ and maximum degree $3$ as a function of its Euler characteristics is studied. The negative solution of an Erdös problem is obtained. A new approach to such problems is proposed which consists in counting the paths between different pairs of vertices in a graph.

All articles are published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/k01/k011/k01110h.htm
Last modified: May 10, 2001