Header menu link for other important links
Partitioning a graph into highly connected subgraphs
, Valentin Borozan, Michael Ferrara, Shinya Fujita, Michitaka Furuya, Yannis Manoussakis, Derrick Stolee
Published in Wiley-Liss Inc.
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.
About the journal
JournalData powered by TypesetJournal of Graph Theory
PublisherData powered by TypesetWiley-Liss Inc.
Open AccessYes
Concepts (7)
  •  related image
    Graph theory
  •  related image
  •  related image
    Degree conditions
  •  related image
    Graph g
  •  related image
  •  related image
    Minimum degree
  •  related image