For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Multiple Graphs Minimizing the Number of Minimum Cut-Sets
Zheng SUN Hiroshi NAGAMOCHI Kikunobu KUSUNOKI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/06/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Graphs and Networks
Full Text: PDF(545.8KB)>>
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.