کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647941 1342384 2013 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Conditions for families of disjoint kk-connected subgraphs in a graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Conditions for families of disjoint kk-connected subgraphs in a graph
چکیده انگلیسی

In [T. Böhme A. Kostochka, Many disjoint dense subgraphs versus large kk-connected subgraphs in large graphs with given edge density, Discrete Math. 309 (4) (2009) 997–1000.], Böhme and Kostochka showed that every large enough graph with sufficient edge density contains either a kk-connected subgraph of order at least rr or a family of rr vertex-disjoint kk-connected subgraphs. Motivated by this, in this note we explore the latter conclusion of their work and give conditions that ensure a graph GG contains a family of vertex-disjoint kk-connected subgraphs. In particular, we show that a graph of order nn with at least 223ksn120ϵ edges contains a family of ss disjoint kk-connected subgraphs each of order at most ϵnϵn. We also show for k≥2k≥2, the vertices of a graph with minimum degree at least 2kn can be partitioned into kk-connected subgraphs. The degree condition in the latter result is asymptotically the best possible as a function of nn.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 6, 28 March 2013, Pages 760–764
نویسندگان
, , ,