International Journal of Mathematics and Mathematical Sciences
Volume 7 (1984), Issue 2, Pages 351-360
doi:10.1155/S0161171284000375
Bridge and cycle degrees of vertices of graphs
Gary Chartrand1
, Farrokh Saba1
and Nicholas C. Wormald3
1Department of Mathematics, Western Michigan University, Kalamazoo 49008, Michigan, USA
3Department of Mathematics, University of Newcastle, Australia
Abstract
The bridge degree bdeg v and cycle degree cdeg v 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 bdeg v=b and cdeg v=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.