International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 1, Pages 41-48
Smallest cubic and quartic graphs with a given number of cutpoints and bridges
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.
For positive integers and , with even, satisfying the inequalities , the minimum order of a connected cubic graph with bridges and cutpoints is computed. Furthermore, the structure of all such smallest cubic graphs is determined. For each positive integer , the minimum order of a quartic graph with cutpoints is calculated. Moreover, the structure and number of all such smallest quartic graphs are determined.