The minimum number of vertices with girth 6 and degree set D = {r,m}

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

14 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)249-258
Journal / PublicationDiscrete Mathematics
Issue number1-3
Publication statusPublished - 28 Jul 2003
Externally publishedYes


A (D;g)-cage is a graph having the minimum number of vertices, with degree set D and girth g. Denote by f(D;g) the number of vertices in a (D;g)-cage. In this paper it is shown that f({r,m};6)≥2(rm-m+1) for any 2≤r<m, and f({r,m};6)=2(rm-m+1) if either (i) 2≤r≤5 and r<m or (ii) m-1 is a prime power and 2≤r<m. Upon these results, it is conjectured that f({r,m};6)=2(rm-m+1) for any r with 2≤r<m. © 2002 Elsevier B.V. All rights reserved.

Research Area(s)

  • Cage, Degree set, Girth, Symmetric graph

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to