Steklov Institute of Mathematics at St.Petersburg

PREPRINT 13/2015


D. V. KARPOV

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

St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences
dvk@pdmi.ras.ru
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.

   
Key words: graph, connectivity, minimal $k$-connected graph.

. .

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$.    ,    .



  
: , graph, , $k$- .
[Full text: (.pdf.gz)]
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg