Partitioning a Graph into Highly Connected Subgraphs | Zendy

Borozan Valentin | Zendy; Ferrara Michael | Zendy; Fujita Shinya | Zendy; Furuya Michitaka | Zendy; Manoussakis Yannis | Zendy; N Narayanan | Zendy; Stolee Derrick | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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)

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research