Прикладная теория графов

Оптимальные графы с точкой сочленения и заданной рёберной связностью

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

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

Аннотация: Вершинной связностью $k$ называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Рёберной связностью $\lambda$ нетривиального графа называется наименьшее число рёбер, удаление которых приводит к несвязному графу. Д. Фалкерсон и Л. Шепли решали задачу определения минимального числа рёбер в графе с заданным числом вершин $n$ и с заданной рёберной связностью $\lambda$. В работе исследуются минимальные по числу рёбер $n$-вершинные графы, которые имеют заданные значения вершинной и рёберной связности. Основной результат состоит в том, что определяется минимальное число рёбер, которые могут иметь $n$-вершинные графы с точкой сочленения и заданной рёберной связностью $\lambda > 1$: $[ (\lambda n + \lambda + 1)/{2} ]$. Предлагается схема построения графов с таким числом рёбер. Это всегда возможно при $n \geq 2\lambda$.

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

УДК: 519.17

DOI: 10.17223/20710410/70/4