Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 06/2011

С.А. ОБРАЗЦОВА

О ЛОКАЛЬНОЙ СТРУКТУРЕ 9 И 10-СВЯЗНЫХ ГРАФОВ

Санкт-Петербургский государственный университет, С.-Петербург, Россия bantoon@mail.ru

This preprint was accepted April 12, 2011

АННОТАЦИЯ:
В статье рассматриваются минимальные и минимальные по 
стягиванию 9 и 10-связные графы. Для них доказываваются 
нижние оценки на долю вершин степеней 9 и 10 в 
общем числе вершин, соответственно. Полученные нижние 
оценки: 1/2 для обоих случаев.

Ключевые слова: $k$-связность, минимальность, минимальность по стягиванию

S.A. Obraztsova

LOCAL STRUCTURE OF 9 AND 10-CONNECTED GRAPHS

ABSTRACT:
We show, that if graph on $n$ vertices is mimimally 
and contraction critically $k$-connected, 
then it has at least $n/2$ vertices of degree $k$ for $k=9,10$.

Key words: $k$-connectivity, minimally $k$-connected, contraction critically $k$-connected

[Full text: Preprint in Russian (.pdf.gz)

Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg