5
$\begingroup$

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

$\endgroup$
5
  • 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$ Commented Feb 4, 2013 at 22:11
  • 1
    $\begingroup$ Please define $\omega(n)$. $\endgroup$ Commented Feb 4, 2013 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
    Commented Feb 5, 2013 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
    Commented Feb 5, 2013 at 20:56
  • 1
    $\begingroup$ Please write all the conditions in the question (even if they are not rigorously defined). $\endgroup$ Commented Feb 6, 2013 at 4:15

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • 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$ Commented Feb 9, 2013 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
    Commented Feb 9, 2013 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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