Steklov Institute of Mathematics at St.Petersburg

PREPRINT 13/2015

MINIMAL k-CONNECTED GRAPHS WITH SMALL NUMBER OF VERTICES OF DEGREE k

This preprint was accepted December 18, 2015

ABSTRACT:   
   Let $n= (2k-1)t+2\ell$, where $k,t, \ell$ are positive integers, such that   $k \ge 3$  and $2\le \ell < {8k+1  \over 9}.$ 
It is proved that any minimal  $k$-connected graph on  $n $ vertices has at least 
$  \lceil{(k-1)v(G)+2k\over 2k-1}  \rceil +1$ vertices of degree~$k$. An infinite series of graphs, for which this bound is attained are constructed.

   

Д. В. КАРПОВ

МИНИМАЛЬНЫЕ k-СВЯЗНЫЕ ГРАФЫ С МАЛЫМ ЧИСЛОМ ВЕРШИН СТЕПЕНИ k

АННОТАЦИЯ   Пусть $n= (2k-1)t+2\ell$, где $k,t, \ell$ --- такие натуральные числа, что    $k \ge 3$  и $2\le \ell < {8k+1  \over 9}.$ 
Доказано, что любой минимальный   $k$-связный граф на $n $ вершинах имеет не менее
$  \lceil{(k-1)v(G)+2k\over 2k-1}  \rceil +1$ вершин степени~$k$. ПОстроена бесконечная серия примеров, для которых оценка достигается.