On Order Degree Problem for Moore Bound

Abstract

The degree diameter problem is a quest to determine the largest graph in terms of vertices satisfying given degree and diameter constraints. The largest possible graphs that can exist and that are subject to degree and diameter constraints are called Moore graphs. Since Moore graphs are rare, researchers are eager to build graphs closer to Moore graphs. This paper discusses the possibility of constructing graphs closer to Moore graphs, keeping a fixed order and minimizing the number of vertex pairs that break the diameter constraint, and suggests a new general relative index that measures the closeness to optimality. Based on the proposed index, it is highlighted that some of the graphs constructed in this work are closer to Moore graphs than the existing best results in the degree diameter problem. Furthermore, a fitness landscape analysis is conducted to identify the nature and the difficulty of the problem. This new method can be considered a new approach to constructing graphs closer to Moore graphs.