Graphs with largest number of minimum cuts (Q1917282)

Denote by \(\sigma(n,k)\) the largest number of minimal cuts in a \(k\)-connected multigraph with \(n\) vertices. It is known that \(\sigma(n,k)\leq(\begin{smallmatrix} n\\ 2\end{smallmatrix})\) if \(n\) is even and this bound is tight. The authors prove that for an odd \(k\geq 3\) it holds \(\sigma(n,k)\leq \lfloor 3n/2\rfloor-2\) and characterize the graphs with \(n\geq 4\) vertices for which this bound is tight. A similar question is also studied for simple graphs, where the corresponding number is denoted by \(\sigma_1(n,k)\). For even \(k\geq 4\) it is shown that \(\sigma_1(n,k)\leq 2(n/k+1)^2+n(k-1)/(k+1)\) and that this bound is tight if \(k+1\) divides \(n\). For odd \(k\geq 7\) it is proved that \(\sigma_1(n,k)\leq(1+4/(k+5))n\). For \(k=3\) and \(k=5\) all extremal graphs are characterized.