<p>In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges  that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).</p>

<p>One could start with these graphs and then perturb them by adding and removing edges without changing the connectivity. The graphs will not be bipartite, however.</p>

<p>Another easy way of creating random graphs with a certain edge-connectivity value is to exploit those cases in which edge-connectivity and minimum degree are identical since creating random graphs with a fixed minimum degree is much easier. Such conditions, also for bipartite graphs, are discussed for example in the paper <a href="http://dml.cz/bitstream/handle/10338.dmlcz/107335/ArchMath_025-1989-1_4.pdf" rel="nofollow">On equality of edge-connectivity and minimum degree of a graph</a> by Plesník and Znám.</p>

CC BY-SA 3.0
2016-09-28T18:38:03.450Z
This is fantastic, thank you!  Although the Harary paper is not for bipartite graphs, it's a great starting point.

The reference to the relationship between min degree and edge-connectivity is extremely useful.  In fact, from sampling experiments the equality between the two seems to be quite common -- as least in the bipartite instances I've tried -- so it'll be great to look at this literature.
user1798883
CC BY-SA 3.0
2016-09-28T15:42:34.053Z
2016-09-28T15:42:34.053Z
Christian Komusiewicz
<p>Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?</p>

<p>Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2016-09-27T20:26:19.290Z
Do you care about structure/the graph being different each time? Because you can just make the complete graph on $k$ vertices. Or if you want it bipartite, make the complete bipartite graph $K_{k,k}$.
Ryan Dougherty
CC BY-SA 3.0
2016-09-27T22:00:30.707Z
Yes I'd like it to be different each time, even sparse if possible. A deterministic approach that, for example, gives the same degree sequence each time would be okay as a starting point ... but not the complete graph :)
user1798883
<graph-theory><max-flow-min-cut><bipartite-graphs>
generate a graph with fixed min cut
user1798883
# generate a graph with fixed min cut

(Asked by: username_0 on 2016-09-27)

Is there a constructive way to generate a graph with a fixed min cut equal to $k$?
One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?

Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!

Thanks in advance!

**Tags:** graph-theory, max-flow-min-cut, bipartite-graphs
> **Comments:**
> **username_1**: Do you care about structure/the graph being different each time? Because you can just make the complete graph on $k$ vertices. Or if you want it bipartite, make the complete bipartite graph $K_{k,k}$.  
> **username_0**: Yes I'd like it to be different each time, even sparse if possible. A deterministic approach that, for example, gives the same degree sequence each time would be okay as a starting point ... but not the complete graph :)  

---

## 1 answers

### Answer by username_2 on 2016-09-28. Score: 3

In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).

One could start with these graphs and then perturb them by adding and removing edges without changing the connectivity. The graphs will not be bipartite, however.

Another easy way of creating random graphs with a certain edge-connectivity value is to exploit those cases in which edge-connectivity and minimum degree are identical since creating random graphs with a fixed minimum degree is much easier. Such conditions, also for bipartite graphs, are discussed for example in the paper [On equality of edge-connectivity and minimum degree of a graph](http://dml.cz/bitstream/handle/10338.dmlcz/107335/ArchMath_025-1989-1_4.pdf) by Plesník and Znám.

> **Comments:**
> **username_0**: This is fantastic, thank you!  Although the Harary paper is not for bipartite graphs, it's a great starting point.  The reference to the relationship between min degree and edge-connectivity is extremely useful.  In fact, from sampling experiments the equality between the two seems to be quite common -- as least in the bipartite instances I've tried -- so it'll be great to look at this literature.  

---

