Aside from the cycle graph, are there other simple unweighted graph constructions for which there are $\omega(n)$ distinct min cuts?

  • 4
    $\begingroup$ There are: the graphs with no edges have exponentially many distinct minimum cuts (trivially). If you want a connected graph, how about adding one chord to a cycle? It still has Θ(n^2) distinct minimum cuts. I am not sure if these are what you are looking for, though. $\endgroup$ – Tsuyoshi Ito Feb 4 '13 at 22:11
  • 1
    $\begingroup$ Please define $\omega(n)$. $\endgroup$ – Yoshio Okamoto Feb 4 '13 at 23:18
  • 1
    $\begingroup$ @YoshioOkamoto It is probably some function that asymptotically dominates the linear function. What else could it be? $\endgroup$ – Pål GD Feb 5 '13 at 12:02
  • $\begingroup$ Sorry, I should have been more clear. By $\omega(n)$, I mean the number of min cuts is superlinear in the number of nodes $n$. With the chord idea, I suppose it's easy enough to start with a cycle graph and "pare down" the number of min cuts to be whatever you like. I was hoping though, that there was some other easy examples of connected graphs with large numbers of min cuts which were somehow structured differently than the cycle graph. $\endgroup$ – Frumple Feb 5 '13 at 20:56
  • 1
    $\begingroup$ Please write all the conditions in the question (even if they are not rigorously defined). $\endgroup$ – Tsuyoshi Ito Feb 6 '13 at 4:15

Aside from the cycle graph, I think a nontrivial class of graphs with $\Omega(n^2)$ distinct min cuts are cactuses. A cactus is a connected graph in which every block (a maximal 2-connected subgraph) is a chordless cycle.

EDIT: In case the considered cactus has $n$ nodes and $b$ blocks of order $n_1, n_2, \ldots, n_b$, the number of min cuts is $\Omega\left(\sum_{i=1}^b n_i^2\right)$. As $\sum_{i=1}^b n_i^2 \ge \frac{1}{b} n^2$, the number of min cuts is $\Omega(n^2)$, provided the number of blocks $b$ is bounded.

  • 2
    $\begingroup$ We need to restrict to leaf-free graphs at least. The number of minimum cuts is then the sum of the number of minimum cuts in each block (i.e. cycle). This can be linear, for example if the maximum of the orders of the blocks is bounded. $\endgroup$ – Colin McQuillan Feb 9 '13 at 9:41
  • $\begingroup$ @ColinMcQuillan: By definition, cactuses have no leaves. And you are right! I overlooked the case of bounded cycle lengths. Thank you for your comments. I have edited it accordingly. $\endgroup$ – user13136 Feb 9 '13 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.