International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 1, Pages 41-48
doi:10.1155/S0161171282000052
Smallest cubic and quartic graphs with a given number of cutpoints and bridges
Gary Chartrand1
, Farrokh Saba1
, John K.jun. Cooper3
, Frank Harary4
and Curtiss E. Wall5
1Department of Mathematics, Western Michigan University, Kalamazoo 49008, Michigan, USA
3Department of Mathematics, Eastern Michigan University, Ypsilanti 48197, Michigan, USA
4Department of Mathematics, University of Michigan, Ann Arbor 48104, Michigan, USA
5Department of Mathematics, Old Dominion University, Norfolk 23508, Virginia, USA
Abstract
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.