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


Minimum degree condition for a graph to be knitted
Authors:Runrun Liu  Martin Rolek  Gexin Yu
Abstract:For a positive integer k, a graph is k-knitted if for each subset S of k vertices, and every partition of S into (disjoint) parts S1,,St for some t1, one can find disjoint connected subgraphs C1,,Ct such that Ci contains Si for each it]?{1,2,,t}. In this article, we show that if the minimum degree of an n-vertex graph G is at least n2+k2?1 when n2k+3, then G is k-knitted. The minimum degree is sharp. As a corollary, we obtain that k-contraction-critical graphs are k8-connected.
Keywords:Corresponding author at: Department of Mathematics  The College of William and Mary  Williamsburg  VA  23185  USA    Graph linkage  Minimum degree  Contraction-critical graphs  Connectivity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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