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 |
|
|
