2
$\begingroup$

Among all graphs with $n$ vertices and edge-connectivity exactly $c$ (so the size of the minimum edge cut is $c$), there is a well-known result of Lomonsov and Poleskkii that the cycle graph, which consists of $n$ vertices arranged in a cycle, and $c/2$ parallel edges between adjacent vertices, has the fewest MINIMAL cuts (i.e. cuts of weight exactly c)

What happens if $c$ is odd? Strangely, all the references I can find to this result omit this case.

EDIT: I left out the condition that the graph has the fewest MINIMAL cuts. Sorry.

Improve this question
$\endgroup$
1
  • $\begingroup$ you are writing fewest minimal cuts, which usually stands for inclusion minimal, but then you say that you mean cuts of weight $c$, which are usually called minimum cuts, and are a subset of the miimal cuts. It is very easy to construct graphs with only one minimum cut, so this can not be what you are looking for. For minimal cuts, my answer below still works. Maybe there is yet another condition on the graphs? $\endgroup$
    – Flo Pfender
    Mar 31, 2012 at 6:18

1 Answer 1

Reset to default
1
$\begingroup$

Maybe, I don't quite understand the question, but the answer appears to be a very similar graph:

Take the graph that you are looking for. Now double up certain edges until your smallest cut has size $c+1$. This will not change the number of cuts, as doubling edges does not change this number. Now Lomonosov and Poleskii (I could not look at their article) tell you a lower bound for the number of cuts of that new graph.

On the other hand, take the cycle graph with $(c+1)/2$ parallel edges between adjacent vertices, and delete one edge. This graph (assuming $c>1$) has the same number of cuts as the cycle graph, and edge connectivity exactly $c$.

If you are instead asking for a graph where every minimal cut has size $c$, then this is not the answer...

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .