О минимальном числе вершин и ребер графа с заданными мерами связности

М. Б. Абросимов, Б. А. Теребин

Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского

Аннотация: Вершинной связностью $k(G)$ графа $G$ называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу, т.е. к графу с одной вершиной. Реберной связностью $\lambda(G)$ нетривиального графа $G$ называется наименьшее количество ребер, удаление которых приводит к несвязному графу. Известно, что вершинная связность $k(G)$ графа $G$, реберная связность $\lambda(G)$ и минимальная степень вершины $\delta(G)$ связаны неравенством Уитни: $k(G) \leqslant \lambda(G) \leqslant \delta(G)$. Ранее авторами была решена задача поиска минимального числа вершин и ребер для графов с заданными значениями $k(G)$, $\lambda(G)$ и $\delta(G)$. Данная работа продолжает эти исследования и существенным образом использует полученные результаты. Приводятся формулы, устанавливающие минимальное число вершин и ребер для графов с заданными значениями $k(G)$ и $\lambda(G)$. Рассматриваются графы, которые имеют минимальное число ребер для заданных значений числа вершин $n$, $k(G)$ и $\lambda(G)$. Описывается семейство таких графов, которые имеют $\lceil {\lambda n}/{2} \rceil$ ребер. Частным случаем найденного семейства при $k=\lambda$ являются графы Харари $H_{k,n}$ – $n$-вершинные $k$-связные графы с минимальным числом ребер. Известно, что число ребер в таких графах равно $\lceil {k n}/{2} \rceil$. Результат пересекается и с задачей определения минимального числа ребер в графе для заданных значений числа вершин $n$ и $\lambda(G)$, которая была решена Фалкерсоном и Шепли.
Библиография: 9 названий.

Ключевые слова: теория графов, вершинная связность, реберная связность, неравенство Уитни, граф Харари.

УДК: 519.17

PACS: 02.10.Ox

MSC: 05C40

Поступило: 16.03.2025

DOI: 10.4213/mzm14677