"Записки научных семинаров ПОМИ"
Том 488, стр. 143-167
О вершинах степени 6 минимального и минимального по
стягиванию 6-связного графа
А. В. Пастор
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский политехнический университет
Петра Великого (СПбПУ),
ул. Политехническая, д.29,
195251, Санкт-Петербург, Россия
avpastor@pdmi.ras.ru
- Аннотация:
В работе исследуются вершины степени $6$ минимального и минимального по стягиванию
$6$-связного графа, то есть $6$-связного графа, который теряет $6$-связность как
при удалении, так и при стягивании любого ребра. В работе доказано, что если
вершины $x$ и $z$ такого графа смежны, имеют степень $6$ и не имеют других смежных
вершин степени $6$, то вершины $x$ и $z$ имеют хотя бы 4 общих смежных.
Более того, в этом случае дается детальное описание окрестности множества
$\{x,z\}$. Также в работе построена бесконечная серия примеров минимальных
и минимальных по стягиванию $6$-связных графов, в которых доля вершин
степени 6 составляет ${11\over17}$.
Библ. -- 21 назв.
- Ключевые слова: $k$-связность, минимальный $k$-связный граф, минимальный по стягиванию
$k$-связный граф
[$k$-connectivity, minimally $k$-connected graph, contraction critically $k$-connected graph]
Полный текст(.pdf)