Graphs with Maximum Number of Minimum Cuts

摘要

The structure of minimum cuts, extremal multigraphs and extremal simple graphsare addressed. The following is considered: let sigma(n,k) be the maximum number of minimum cuts in a k connected multigraph with n vertices. Sigma(n,k) are determined and extremal graphs are characterized for every n and k. The same problem is also investigated for graphs with no multiple edges.