Профиль » Публикация

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