Оптимальные графы с точкой сочленения и заданной рёберной связностью | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/4

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