Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts - Archive ouverte HAL Access content directly
Conference Papers Year :

## Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts

(1) , (2, 3) , (2, 3) , (4) , (1) , (2)
1
2
3
4
Alessio Conte
• Function : Author
• PersonId : 991829
Roberto P Grossi
• Function : Author
• PersonId : 857937
Romeo Rizzi
• Function : Author
• PersonId : 977567
Takeaki Uno
• Function : Author
Luca P Versari
• Function : Author
• PersonId : 991831

#### Abstract

We study the number of inclusion-minimal cuts in an undi-rected connected graph G, also called st-cuts, for any two distinct nodes s and t: the st-cuts are in one-to-one correspondence with the partitions $S ∪ T$ of the nodes of G such that $S ∩ T = ∅, s ∈ S, t ∈ T$ , and the sub-graphs induced by S and T are connected. It is easy to find an exponential upper bound to the number of st-cuts (e.g. if G is a clique) and a constant lower bound. We prove that there is a more interesting lower bound on this number, namely, $Ω(m$), for undirected m-edge graphs that are biconnected or triconnected (2-or 3-node-connected). The wheel graphs show that this lower bound is the best possible asymptotically.

#### Domains

Computer Science [cs]

### Dates and versions

hal-01964710 , version 1 (23-12-2018)

### Identifiers

• HAL Id : hal-01964710 , version 1
• DOI :

### Cite

Alessio Conte, Roberto P Grossi, Andrea Marino, Romeo Rizzi, Takeaki Uno, et al.. Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts. WG 2018 - International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2018, Cottbus, Germany. pp.100-110, ⟨10.1007/978-3-030-00256-5_9⟩. ⟨hal-01964710⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

22 View