Partitioning a graph into highly connected subgraphs

DOI10.1002/JGT.21904MaRDI QIDQ3188667zbMATH OpenOpenAlexFDO

Authors V. Borozan, Michael Ferrara, Shinya Fujita, Michitaka Furuya, Narayanan N., Derrick Stolee, Y. Manoussakis

Publication date 12 August 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2696

zbMATH Keywords

\(k\)-proper partition of a graph

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given $kge1$, a $k$-proper partition of a graph $G$ is a partition $mathcalP$ of $V(G)$ such that each part $P$ of $mathcalP$ induces a $k$-connected subgraph of $G$. We prove that if $G$ is a graph of order $n$ such that $delta(G)gesqrtn$, then $G$ has a $2$-proper partition with at most $n/delta(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 $delta(G)gesqrtc(k-1)n$, where $c=frac2123180$, then $G$ has a $k$-proper partition into at most $fraccndelta(G)$ parts. This improves a result of Ferrara, Magnant and Wenger [Conditions for Families of Disjoint $k$-connected Subgraphs in a Graph, Discrete Math. 313 (2013), 760--764] and both the degree condition and the number of parts are best possible up to the constant $c$.

Recommendations

• Partitions of graphs with high minimum degree or connectivity.
• Bipartition of graph under degree constraints
• Degree-constrained 2-partitions of graphs
• On connected partition with degree constraints
• Partitioning a k-connected graph

Cites work

• A clustering algorithm based on graph connectivity
• A look at cycles containing specified elements of a graph
• Advances on the Hamiltonian problem -- a survey
• Conditions for families of disjoint \(k\)-connected subgraphs in a graph
• Factors and factorizations of graphs. Proof techniques in factor theory
• Graph decomposition with constraints on the connectivity and minimum degree
• Graph factors and factorization: 1985--2003: a survey
• scientific article; zbMATH DE number 2191994 (Why is no real title available?)
• Making the components of a graph \(k\)-connected
• Note on Hamilton Circuits
• On the editing distance of graphs
• Partition of graphs with condition on the connectivity and minimum degree
• Recent advances on the Hamiltonian problem: survey III
• Updating the hamiltonian problem—A survey
• What is the furthest graph from a hereditary property?

Cited in

(16)

• On the complexity of partitioning graphs into connected subgraphs
• Partitions of graphs with high minimum degree or connectivity.
• Highly connected subgraphs of graphs with given independence number
• 2-proper partition of a graph
• Bipartition of graph under degree constraints
• On partitioning the edges of graphs into connected subgraphs
• On a graph partition result of Kűhn and Osthus.
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• scientific article; zbMATH DE number 7101993 (Why is no real title available?)
• Partitioning a k-connected graph
• scientific article; zbMATH DE number 4187858 (Why is no real title available?)
• On partitioning a graph into two connected subgraphs
• Partitioning graphs with linear minimum degree
• New invariants for partitioning a graph into 2-connected subgraphs
• Perfect hierarchical matchings in graphs

This page was built for publication: Partitioning a graph into highly connected subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188667)