首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Partition conditions and vertex-connectivity of graphs
Authors:Ervin Győri
Institution:(1) Mathematical Institute of the Hungarian Academy of Sciences, H-1053 Budapest, Hungary
Abstract:It was proved (5], 6]) that ifG is ann-vertex-connected graph then for any vertex sequencev 1, ...,v n V(G) and for any sequence of positive integersk 1, ...,k n such thatk 1+...+k n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv 1, ...,v(n), and the class of the partition containingv i induces a connected subgraph consisting ofk i vertices, fori=1, 2, ...,n. Now fix the integersk 1, ...,k n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv 1, ...,v n V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.
Keywords:05 C 40
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号