"Записки научных семинаров ПОМИ"
Том 450 , стр. 151-174
Верхняя оценка количества рёбер в графе, дополнение $k$-ой степени которого связно
В. С. Самойлов
С.-Петербургский государственный университет, Математико-механический факультет,
Университетский пр. 28, Старый Петергоф, 198504, Санкт-Петербург, Россия
sammarize@gmail.com
- Аннотация:
Назовем граф $k$-{\em широким}, если для любого разбиения его вершин на два множества, в них найдутся вершины на растоянии не менее $k$
(то есть, дополнение $k$ степени этого графа связно).
Назовем граф $k$-{\em моношироким}, если для любого разбиения его вершин на два множества, в них найдутся вершины на растоянии $k$.
В работе доказано, что в дополнении 3-широкого графа на $n$ вершинах не менее чем $3n-7$ ребер, а в дополнении 3-моноширокого графа на
$n$ вершинах не менее чем $3n-8$ ребер. Приводятся бесконечные серии примеров, подтверждающих точность оценок.
Также доказана асимптотически точная оценка для случая $k\ge 4$: в дополнении $k$-широкого графа не менее чем $(n-2k)\left(2k - 4[\log_2k] -1\right)$ рёбер.
Библ. -- 6 назв.
- Ключевые слова: экстремальная теория графов, степень графа, расстояние в графе
[extremal graph theorey, a power of a graph, distance in a graph]
Полный текст(.pdf)