Partitioning graphs into $k$-connected induced subgraphs

Problem and Results Summary

For $k \geq 1$, if a graph $G$ has $\delta(G) \geq \frac{n(G)+k-2}{2}$, then $G$ is $k$-connected. This minimum-degree condition is sharp.

What if instead of having all of $G$ be $k$-connected, it sufficed to partition $V(G)$ into (not too many!) parts, each of which induces a $k$-connected subgraph?
Such a partition is *$k$-proper*.
Such a tool could be used to help in clustering applications in social networks.

We seek a sharp minimum-degree condition that implies that $G$ has a $k$-proper partition.

**Conjecture.**
If $\delta(G) \geq \sqrt{(k-1)n}$, then $G$ has a $k$-proper partition with at most $\frac{n-k+1}{\delta(G)-k+2}$ parts.

Ferrara *et. al* find that the conjecture holds for $k=2$.
Also, if $\delta(G) \geq \sqrt{c(k-1)n}$, for $c = \frac{2123}{180}$, then $G$ has a $k$-proper partition into $\frac{cn}{\delta(G)}$ parts.
If we relax the condition that the number of parts is bounded by a ratio of $n/\delta(G)$, then the minimum degree condition can be relaxed to $\delta(G) \geq \sqrt{\frac{193}{30}(k-1)n}$.

Research Papers

V. Borozan, M. Ferrara, S. Fujita, M. Furuya, Y. Manoussakis, Narayanan N, and D. Stolee,
Partitioning a graph into highly connected subgraphs,
to appear in *Journal of Graph Theory*.

Web Version ArXiv Version Official Version

Web Version ArXiv Version Official Version

Related Work

Presentations