Search

For positive integers b and c, with c even, satisfying the inequalities b+1≤c≤2b, the minimum order of a connected cubic graph with b bridges and c cutpoints is computed. Furthermore, the structure of all such smallest cubic graphs is determined. For each positive integer c, the minimum order of a quartic graph with c cutpoints is calculated. Moreover, the structure and number of all such smallest quartic graphs are determined.

The bridge degree bdeg v and cycle degree cdeg v of a vertex v in a graph G are, respectively, the number of bridges and number of cycle edges incident with v in G. A characterization of finite nonempty sets S of nonnegative integers is given for which S is the set of bridge degrees (cycle degrees) of the vertices of some graph. The bridge-cycle degree of a vertex v in a graph G is the ordered pair (b,c), where bdeg v=b and cdeg v=c. Those finite sets S of ordered pairs of nonnegative integers for which S is the set of bridge-cycle degrees of the vertices of some graph are also characterized.