Smallest cubic and quartic graphs with a given number of cutpoints and bridges. (1982) - Chartrand, Gary; Saba, Farrokh; Cooper, John K.; Harary, Frank; Wall, Curtiss E.
Abstract : For positive integersb andc, withc even, satisfying the inequalitiesb + 1 ≤ c ≤ 2 b, the minimum order of a connected cubic graph withb bridges andc cutpoints is computed. Furthermore, the structure of all such smallest cubic graphs is determined. For each positive integerc, the minimum order of a quartic graph withc cutpoints is calculated. Moreover, the structure and number of all such smallest quartic graphs are determined.