Premium
Regular graphs with given girth pair
Author(s) -
Harary Frank,
Kovács Peter
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070210
Subject(s) - mathematics , combinatorics , odd graph , girth (graph theory) , discrete mathematics , triangle free graph , graph , chordal graph , 1 planar graph
The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is proved that two of these families consist of smallest graphs.