|
Zapiski Nauchnykh Seminarov POMI, 2011, Volume 391, Pages 157–197
(Mi znsl4572)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Local structure of 9 and 10-connected graphs
S. A. Obraztsova Nanyang Technological University, Singapore
Abstract:
In his paper R. Halin (in “Recent Progress in Combinatorics”, Academic Press, 1969) discusses, what is 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$. Twenty years later the exact bound for $k=4$ ($c_4=1$) was found by N. Martinov and, independently, by M. Fontet. For larger $k$ exact bounds are unknown.
This paper contributes to the study of local structure of minimally and contraction critically $k$-connected graphs and lower bounds for $c_k$. It was proved that $c_k\geq\frac12$ for $k=9,10$. This result extends the sequence of the lower bounds for $c_k$ which is equal to $\frac12$ to $k=6,7,8,9,10$.
Key words and phrases:
$k$-connectivity, minimally $k$-connected, contraction critically $k$-connected, lower bounds.
Received: 12.10.2011
Citation:
S. A. Obraztsova, “Local structure of 9 and 10-connected graphs”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 157–197; J. Math. Sci. (N. Y.), 184:5 (2012), 634–654
Linking options:
https://www.mathnet.ru/eng/znsl4572 https://www.mathnet.ru/eng/znsl/v391/p157
|
Statistics & downloads: |
Abstract page: | 120 | Full-text PDF : | 34 | References: | 28 |
|