FPM 2001, ТОМ 7, ВЫПУСК 4, СТР. 1203-1225

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

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

С. А. Тищенко

Аннотация

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



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

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

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