Premium
On the genus of five‐ and six‐regular graphs
Author(s) -
Proulx Viera Krňanová
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.3190070212
Subject(s) - mathematics , corollary , combinatorics , conjecture , genus , strongly regular graph , clique sum , indifference graph , chordal graph , 1 planar graph , discrete mathematics , pathwidth , graph , line graph , botany , biology
This paper shows how to construct infinitely many regular graphs of degrees five and six having given genus γ > 0, which settles favorably Conjecture 1 stated by T. W. Tucker. Tucker has shown that there are infinitely many regular graphs of degrees four and three of arbitrary given genus (Theorem 1). He also proved that the number of regular graphs of degree greater than six embeddable in a given surface is finite (Corollary to Proposition 1). The case of the regular graphs of degrees six and five was left unanswered (Conjecture 1). This paper also shows a new way of constructing infinitely many regular graphs of degrees three and four of arbitrary genus γ > 0.