Partitioning a Graph into Highly Connected Subgraphs |
| |
Authors: | Valentin Borozan Michael Ferrara Shinya Fujita Michitaka Furuya Yannis Manoussakis Narayanan N Derrick Stolee |
| |
Institution: | 1. L.R.I.,B?T.490, UNIVERSITY PARIS 11 SUD, ORSAY CEDEX, FRANCE;2. ALFRéD RéNYI INSTITUTE OF MATHEMATICS, HUNGARIAN ACADEMY OF SCIENCES, BUDAPEST, HUNGARY;3. DEPARTMENT OF MATHEMATICAL AND STATISTICAL SCIENCES, UNIVERSITY OF COLORADO DENVER, DENVER, COLORADO;4. INTERNATIONAL COLLEGE OF ARTS AND SCIENCES, YOKOHAMA CITY UNIVERSITY, KANAZAWA‐KU, YOKOHAMA, JAPAN;5. DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE, TOKYO UNIVERSITY OF SCIENCE, SHINJUKU‐KU, TOKYO, JAPAN;6. DEPARTMENT OF MATHEMATICS, INDIAN INSTITUTE OF TECHNOLOGY MADRAS, CHENNAI, INDIA;7. DEPARTMENT OF MATHEMATICS, DEPARTMENT OF COMPUTER SCIENCE, IOWA STATE UNIVERSITY, AMES, IOWA |
| |
Abstract: | Given , a k‐proper partition of a graph G is a partition of such that each part P of induces a k‐connected subgraph of G. We prove that if G is a graph of order n such that , then G has a 2‐proper partition with at most 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 where , then G has a k‐proper partition into at most 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. |
| |
Keywords: | |
|
|