Оптимальные реализации графов с заданными мерами связности

Вершинной связностью $k(G)$ графа $G$ называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу, т.е. к графу с одной вершиной. Реберной связностью $\lambda(G)$ нетривиального графа $G$ называется наименьшее количество ребер, удаление которых приводит к несвязному графу. Вершинная связность $k(G)$, реберная связность $\lambda(G)$ и минимальная степень вершины $\delta(G)$ графа связаны неравенством, которое было найдено Уитни в 1932 году: $k(G) \leq \lambda(G) \leq \delta(G)$. Позднее Чартрэнд и Харари доказали, что для любых натуральных чисел $a$, $b$, $c$, таких что $0 < a \leq b \leq c$, существует граф $G$, у которого $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$. В доказательстве строится семейство графов с указанными выше характеристиками, каждый из которых имеет $2(c+1)$ вершин и $c(c+1)+b$ ребер. Однако, легко заметить, что в некоторых случаях можно построить подходящий граф с меньшим числом вершин и ребер. Например, если $a=b=c$, то соответствующей оптимальной реализацией является полный граф на $c+ 1$ вершинах. В данной работе рассматривается вопрос минимизации конструкции Чартрэнда–Харари. Показывается, что при $b=c$ можно построить граф с меньшим числом вершин. Отдельно рассматриваются четыре случая: $a=b=c$, $a < b < c$, $a=b < c$ и $a < b=c$. Для каждого случая предлагаются графы с заданными значениями $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$ с минимальным числом вершин и с минимальным числом ребер.
Библиография: 6 названий.