ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2001, ТОМ 7, ВЫПУСК 4, СТР. 1203-1225

Максимальный размер графа диаметра 2 с фиксированной эйлеровой характеристикой

С. А. Тищенко

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

Найден точный максимальный размер планарного графа диаметра $2$ с фиксированной максимальной степенью вершин $$D £ 7. Для решения этой проблемы использован метод вырожденных путей. Доказано, что размер $2$D +1 ($3$£ D £ 4) и $$D +5 ($5$£ D £ 7) является максимально возможным. Этот результат завершает анализ проблемы размера--диаметра планарных графов диаметра $2$. В случае $$D £ 6 также найден максимальный размер графов диаметра $2$, допускающих вложение в проективную плоскость и тор.

Полнотекстовая версия статьи в формате PostScript (243 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k01/k014/k01414h.htm.
Изменения вносились 17 апреля 2002 г.