2
$\begingroup$

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.

Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ follows a particular random graph model? Or if it is bipartite?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You might be interested in the following paper of Bollobas: sciencedirect.com/science/article/pii/0012365X79901390 What you say is that the edge-connectivity is at most the average degree (and then at most the minimum degree if the graph is regular), and the paper above looks at sufficient conditions for it to be an equality. $\endgroup$
    – Louis Esperet
    Commented Nov 17, 2016 at 8:22
  • $\begingroup$ @LouisEsperet do you know if there are any special results for bipartite graphs? $\endgroup$
    – user1798883
    Commented Nov 18, 2016 at 17:29
  • 1
    $\begingroup$ Bollobas used his result (mentioned above) to prove that for almost every graph, the minimum degree and the edge-connectivity coincide (this is a simple consequence of the fact that almost every graph has diameter 2). See page 18 of sciencedirect.com/science/article/pii/0012365X81902533 The same argument does not work for random bipartite graphs (they don't have diameter 2). But I'm fairly confident that the statement remains true for random bipartite graphs. $\endgroup$
    – Louis Esperet
    Commented Nov 21, 2016 at 8:05

0

Reset to default

You must log in to answer this question.