Get all the updates for this publication

Articles

Partitioning a graph into highly connected subgraphsOpen Access

Published in Wiley-Liss Inc.

2016

DOI: 10.1002/jgt.21904

Volume: 82

Issue: 3

Pages: 322 - 333

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=2123180, then G has a k-proper partition into at most cnδ(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. © 2015 Wiley Periodicals, Inc.

Preprint Version

Content may be subject to copyright.This is a green open access articleThis is a green open access article

About the journal

Journal | Data powered by TypesetJournal of Graph Theory |
---|---|

Publisher | Data powered by TypesetWiley-Liss Inc. |

ISSN | 03649024 |

Open Access | Yes |

Concepts (7)

- Graph theory
- CONNECTED SUBGRAPHS
- Degree conditions
- Graph g
- K-CONNECTED
- Minimum degree
- Geometry