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

ПРЕПРИНТ 05/2011

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

This preprint was accepted March 17, 2011

АННОТАЦИЯ:
В статье
[4] Р. Халиным был задан вопрос о том, какова наибольшая константа $c_k$, 
такая, что количество вершин степени $k$ в минимальном и минимальном 
по стягиванию $k$-связном графе $G$ равно по крайней мере $c_k|G|$. 
На настоящий момент для $k=4$ известна точная оценка (а именно $c_4=1$) 
и для $k \geq 5$ неизвестно никаких верхних оценок. 
В этой статье доказываются верхние оценки для $c_k$ при всех $k \geq 5$.

S.A. Obraztsova, A.V. Pastor

ABOUT VERTICES OF DEGREE k OF MINIMALLY AND CONTRACTION CRITICALLY k-CONNECTED GRAPHS: UPPER BOUNDS

ABSTRACT:
In his article [4] R.\,Halin asked, what the constant $c_k$ 
such that any minimally and contraction critically $k$-connected graph has at least $c_k|V(G)|$ vertices of degree $k$. Exact bound for $k=4$ ($c_4=1$)
  and no upper bound for larger $k$ is known now. 
We found upper bounds for $c_k$ for $k \geq 5$.

 Key words: k-connectivity, minimally k-connected, contraction critically k-connected, upper bounds



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


 







Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg