International Journal of Mathematics and Mathematical Sciences
Volume 7 (1984), Issue 2, Pages 351-360

Bridge and cycle degrees of vertices of graphs

Gary Chartrand,1 Farrokh Saba,1 and Nicholas C. Wormald2

1Department of Mathematics, Western Michigan University, Kalamazoo 49008, Michigan, USA
2Department of Mathematics, University of Newcastle, Australia

Received 2 February 1982

Copyright © 1984 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.


The bridge degree bdegv and cycle degree cdegv of a vertex v in a graph G are, respectively, the number of bridges and number of cycle edges incident with v in G. A characterization of finite nonempty sets S of nonnegative integers is given for which S is the set of bridge degrees (cycle degrees) of the vertices of some graph. The bridge-cycle degree of a vertex v in a graph G is the ordered pair (b,c), where bdegv=b and cdegv=c. Those finite sets S of ordered pairs of nonnegative integers for which S is the set of bridge-cycle degrees of the vertices of some graph are also characterized.