Premium
The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
Author(s) -
Bixby R. E.
Publication year - 1975
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1975.5.3.253
Subject(s) - combinatorics , mathematics , minification , graph , enhanced data rates for gsm evolution , connectivity , discrete mathematics , computer science , mathematical optimization , telecommunications
The problem studied is the following: What is the minimum number of edges and vertices in a graph with edge connectivity n and exactly m n‐bonds (cuts)? It is perhaps surprising that this problem turns out to have an essentially closed form solution for all m and n (Theorem C at the end of Section 5). Furthermore, the methods employed make it possible, for many values of m and n, to actually write down a graph that achieves the minimum. These methods involve, as an interesting by‐product, estimating the solutions of integer minimization problems of the form where k varies as part of the minimization. In particular, it is shown that the obvious “greedy” algorithm (i.e., choose r 0 as large as possible, then r 1 as large as possible and so forth until m is exhausted) almost works.