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 Chartrand,1 Farrokh Saba,1 John K. Cooper Jr.,2 Frank Harary,3 and Curtiss E. Wall4

1Department of Mathematics, Western Michigan University, Kalamazoo 49008, Michigan, USA
2Department of Mathematics, Eastern Michigan University, Ypsilanti 48197, Michigan, USA
3Department of Mathematics, University of Michigan, Ann Arbor 48104, Michigan, USA
4Department of Mathematics, Old Dominion University, Norfolk 23508, Virginia, USA

Received 6 April 1981

Copyright © 1982 Gary Chartrand et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.