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 ![urn:x-wiley:03649024:media:jgt21904:jgt21904-math-0007]( "urn:x-wiley:03649024:media:jgt21904:jgt21904-math-0007") 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: | |
|
|
