TL;DR
This paper investigates "arbitrarily partitionable" graphs, which model networks that can be broken down into any specified number of connected subnetworks. The authors show that unlike related graph properties, arbitrarily partitionable graphs can have an arbitrarily large number of components after removing a small set of vertices (a cutset), though the sizes of these components grow exponentially.
What Problem Does This Paper Address?
Imagine a computer network represented as a graph, where computers are vertices and connections are edges. An "arbitrarily partitionable" (AP) graph is one where you can always divide the network into any number of smaller, connected subnetworks of specified sizes. This is a desirable property for network resilience and management. The paper delves into the structural properties of these AP graphs, particularly focusing on what happens when you remove a small number of vertices (a "cutset"). Previous research had established bounds on the number of components formed after removing a cutset for related graph properties like OLAP (on-line arbitrarily partitionable) and RAP (recursively arbitrarily partitionable). This paper addresses the question of whether similar bounds exist for AP graphs, especially for cutsets of size 2 or more.
Methods
The paper employs a combination of theoretical graph constructions and proofs by induction. For proving that AP graphs can have arbitrarily many components after removing a cutset, the authors construct specific graph families. These constructions involve building graphs based on cliques and paths, carefully choosing vertex and edge configurations to satisfy the AP property. For analyzing the size of components, they utilize lemmas that establish relationships between component sizes and the properties of AP graphs, often relying on the definition of AP graphs and properties of decompositions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Arbitrary Components, Exponential Sizes: The most striking finding is that for AP graphs, removing a cutset of size $k \ge 2$ does not limit the number of resulting components. This contrasts with related properties like OLAP and RAP. However, the sizes of these components are forced to grow exponentially with their number, preventing them from being arbitrarily small.
- Construction of AP Graphs: The paper provides explicit constructions for AP graphs that exhibit this property of having many components after cutset removal. These constructions involve carefully designed graphs based on cliques and paths, ensuring the AP property is maintained.
- Distinction from OLAP/RAP: The results highlight a significant structural difference between AP graphs and their "on-line" (OLAP) and "recursive" (RAP) counterparts. While OLAP and RAP graphs have stricter bounds on component numbers after cutset removal, AP graphs are more flexible in this regard.
- Exponential Growth as a Constraint: The exponential growth of component sizes acts as a crucial constraint, preventing an AP graph from being "too fragmented" in a way that might be problematic for network partitioning.
Key Results
- Theorem 10: For any integers $k \ge 2$ and $c > 2$, there exists an AP graph $G$ with connectivity $k$ such that for every $k$-element cutset $S$ of $G$, $G[V \setminus S]$ consists of exactly $c$ components.
- Theorem 12: For an AP graph $G$ with $n$ vertices, if $S$ is a cutset of size $k$, and $C_1, \dots, C_l$ are the orders of the components of $G[V \setminus S]$ with $l > k$ and $1 < C_1 < C_2 < \dots < C_l$, then the sequence $(C_i)_{i>1}$ grows exponentially with $i$.
Limitations and Future Work
- Gap in Bounds: The paper notes that while an exponential lower bound on component size growth is established, there's a significant gap between this bound and the sizes of components in the constructed examples. This suggests potential for tighter bounds or smaller examples.
- Specific Graph Families: The constructions for Theorem 10 focus on specific graph families (cliques and paths, balloons). Exploring other graph structures that are AP and exhibit this component behavior could be a future direction.
- Practical Implications: While the paper is theoretical, further research could explore the practical implications of these findings for designing robust and partitionable networks. Understanding how to construct or identify AP graphs with these properties could be valuable.
Summary updated