The minimum number of edges and vertices in a graph with edge connectivity π and π π-bonds
Robert E. Bixby Β· Bulletin of the American Mathematical Society Β· 1974
The purpose of this note is to announce the closed form solution of the following extremal problem in graph connectivity (see [1] and [2]): compute the minimum number of edges and vertices in a graph with a given edge connectivity and a given number of minimum cardinality bonds.It is hoped that the solution to this problem will be helpful in work on the following apparently quite difficult problem posed by Van Slyke and Frank [7] : given the number of A>sets of edges of a graph containing bonds, what are bounds for the number of &'-sets of edges containing bonds, k'jΒ£k!G denotes a graph with vertex and edge sets V(G) and E(G), both finite.Loops and multiple edges are allowed.A polygon of G is a connected subgraph of valency two.A multigon is a subgraph with at least two edges, that is either a polygon or a link graph after identification of multiple edges.A bond is a minimal nonempty set of edges that meets no polygon in just one edge.We define the edge connectivityFor n and m positive integers putFor definitions of terms not defined here the reader is referred to Tutte [5], [61. AMS (MOS) subject classifications (1970). Primary 05C99, 94A20.