Premium
Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles
Author(s) -
Azarija Jernej,
Klavžar Sandi
Publication year - 2015
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.21837
Subject(s) - combinatorics , mathematics , graph , regular polygon , discrete mathematics , chordal graph , geometry
Let ρ ( G ) denote the number of convex cycles of a simple graph G of order n , size m , and girth 3 ≤ g ≤ n . It is proved that ρ ( G ) ≤ n g ( m − n + 1 )and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.