We study the number of inclusion-minimal cuts in an undirected connected graph G, also called -cuts, for any two distinct nodes s and t: the -cuts are in one-to-one correspondence with the partitions ∪ of the nodes of G such that ∩=∅ , ∈ , ∈ , and the subgraphs induced by S and T are connected. It is easy to find an exponential upper bound to the number of -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, () , 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.
Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts / Alessio Conte; Roberto Grossi; Andrea Marino; Romeo Rizzi; Takeaki Uno; Luca Versari. - STAMPA. - (2018), pp. 100-110. (Intervento presentato al convegno Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018) [10.1007/978-3-030-00256-5_9].
Tight Lower Bounds for the Number of Inclusion-Minimal st-Cuts
Roberto Grossi;Andrea Marino;
2018
Abstract
We study the number of inclusion-minimal cuts in an undirected connected graph G, also called -cuts, for any two distinct nodes s and t: the -cuts are in one-to-one correspondence with the partitions ∪ of the nodes of G such that ∩=∅ , ∈ , ∈ , and the subgraphs induced by S and T are connected. It is easy to find an exponential upper bound to the number of -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, () , 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.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.