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

ПРЕПРИНТ 01/2010

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

This preprint was accepted February 19, 2010

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

S.A. Obraztsova

A LOCAL STRUCTURE OF 5 AND 6-CONNECTED GRAPHS

ABSTRACT:
We show, that if 5-connected graph on n vertices has no 
contractible, neither non-essential edges then 
it has 4/7n vertices of degree 5. We also show, that 
if 6-connected graph on n vertices has no contractible, 
neither non-essential edges then it has 1/2n 
vertices of degree 6.