Bridge and Cycle Degrees of Vertices of Graphs

Gary Chartrand, Farrokh Saba, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review


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.

Original languageEnglish
Pages (from-to)351-360
Number of pages10
JournalInternational Journal of Mathematics and Mathematical Sciences
Issue number2
Publication statusPublished - 1984
Externally publishedYes


  • Bridge degree
  • bridge-cycle degree
  • cycle degree

Cite this