Multiple Graphs Minimizing the Number of Minimum Cut-Sets

Zheng SUN  Hiroshi NAGAMOCHI  Kikunobu KUSUNOKI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.6   pp.915-921
Publication Date: 1990/06/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 


Full Text: PDF(545.8KB)>>
Buy this Article




Summary: 
The method of constructing a graph G with the maximum cardinality of minimum cut-sets, which is 2e/n, has been obtained by Harary in 1962, where n is the number of nodes and e is the number of edges. Afterward, the problem of finding a simple graph G which minimizes the number of minimum cut-sets with cardinality 2e/n subject to λ(G)2e/n was solved by Bauer, Boesch, Suffel and Tindell in 1985. Generalizing this, a necessary and sufficient condition for a simple graph with n nodes and e edges to minimize the number of cut-sets with cardinality z has been recently presented by Sun, Nagamochi and Kusunoki in 1989, where z is chosen such that 2e/nz22e/n3 for2e/n3, or z2, 3, for2e/n2. In this paper, we generalize the above results to multiple graphs, and give a necessary and sufficient condition for a multiple graph G with n nodes and e edges to minimize the number of minimum cut-sets whose cardinality is2e/n.