Premium
Partitioning a Graph into Highly Connected Subgraphs
Author(s) -
Borozan Valentin,
Ferrara Michael,
Fujita Shinya,
Furuya Michitaka,
Manoussakis Yannis,
N Narayanan,
Stolee Derrick
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21904
Subject(s) - frequency partition of a graph , partition (number theory) , combinatorics , mathematics , graph , degree (music) , induced subgraph , graph partition , distance hereditary graph , factor critical graph , discrete mathematics , graph power , line graph , physics , acoustics , vertex (graph theory)
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 mostc 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 .