Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles |
| |
Authors: | Jernej Azarija Sandi Klavžar |
| |
Affiliation: | 1. INSTITUTE OF MATHEMATICS, PHYSICS, AND MECHANICS, JADRANSKA 19, SLOVENIA;2. FACULTY OF MATHEMATICS AND PHYSICS, UNIVERSITY OF LJUBLJANA, JADRANSKA 19, SLOVENIA;3. FACULTY OF NATURAL SCIENCES AND MATHEMATICS, UNIVERSITY OF MARIBOR, KORO?KA 160, SLOVENIA |
| |
Abstract: | Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that 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. |
| |
Keywords: | convex subgraph convex cycle Moore graph extremal graph 05C75 05C12 |
|
|