Partitioning a Graph into Highly Connected Subgraphs. Issue 3 (17th August 2015)

• Record Type: Journal Article
• Authors: Borozan, Valentin; Ferrara, Michael; Fujita, Shinya; Furuya, Michitaka; Manoussakis, Yannis; N, Narayanan; Stolee, Derrick
• Is Part Of: Journal of graph theory. Volume 82:Issue 3(2016)
• Page Start: 322
• Page End: 333
• Publication Date: 2015-08-17
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21904
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Given k ≥ 1, a k ‐ proper partition of a graph G is a partition P of V ( G ) such that each part P of P induces a k ‐connected subgraph of G . We prove that if G is a graph of order n such that δ ( G ) ≥ n, then G has a 2‐proper partition with at most n / δ ( G ) parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if G is a graph of order n with minimum degree δ ( G ) ≥ c ( k − 1 ) n, where c = 2123 180, then G has a k ‐proper partition into at most c n δ ( G ) parts. This improves a result of Ferrara et al. ( Discrete Math 313 (2013), 760–764), and both the degree condition and the number of parts is best possible up to the constant c .