International Journal of Mathematics and Mathematical Sciences
Volume 12 (1989), Issue 2, Pages 305-308
doi:10.1155/S0161171289000359
On the number of cut-vertices in a graph
Department of Mathematics, University of Mississippi, University 38677, MS, USA
Received 18 May 1987; Revised 8 September 1987
Copyright © 1989 Glenn Hopkins and William Staton. 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
A connected graph with n vertices contains no more than r2r-2(n-2) cutvertices
of degree r. All graphs in which the bound is achieved are described. In
addition, for graphs of maximum degree three and minimum δ, best possible bounds are
obtained for δ=1, 2, 3.