|
Фундаментальная и прикладная математика, 2001, том 7, выпуск 4, страницы 1203–1225
(Mi fpm622)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Максимальный размер графа диаметра 2 с фиксированной эйлеровой характеристикой
С. А. Тищенко Государственный лицей "Вторая школа"
Аннотация:
Найден точный максимальный размер планарного графа диаметра 2 с фиксированной максимальной степенью вершин $\Delta\leq7$. Для решения этой проблемы использован метод вырожденных путей. Доказано, что размер $2\Delta+1$ ($3\leq\Delta\leq4$) и $\Delta+5$ ($5\leq\Delta\leq7$) является максимально возможным. Этот результат завершает анализ проблемы размера–диаметра планарных графов диаметра 2. В случае $\Delta\leq6$ также найден максимальный размер графов диаметра 2, допускающих вложение в проективную плоскость и тор.
Ключевые слова:
теория графов, проблема размера–диаметра, диаметр графа, эйлерова характеристика, максимальный размер графа.
Поступила в редакцию: 01.06.2000
Образец цитирования:
С. А. Тищенко, “Максимальный размер графа диаметра 2 с фиксированной эйлеровой характеристикой”, Фундамент. и прикл. матем., 7:4 (2001), 1203–1225
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/fpm622 https://www.mathnet.ru/rus/fpm/v7/i4/p1203
|
Статистика просмотров: |
Страница аннотации: | 377 | PDF полного текста: | 419 | Первая страница: | 1 |
|