Description
The Moore bound was introduced over 50 years ago as both a lower bound on the order of cages (k-regular graphs of girth g with minimal number of vertices) and an upper bound on the order of the largest graphs of maximum degree k and diameter d. Even though it is known to be sharp for both problems, the sets of parameters for which there exist graphs of orders equal to the Moore bound are very limited (and classified), and the difference between the Moore bound and the orders of the extremal graphs for the rest of the parameters is not well understood. All the known constructions for these parameters seem to suggest that the Moore bound is a rather bad predictor of the orders of the extremal graphs. However, improved bounds are very hard to find, and the known improvements differ from the Moore bounds by at most 4 vertices.
In our talk we present attempts at improving the Moore bound via counting cycles in the (potential) cages based on divisibility conditions that have to be satisfied by the numbers of cycles rooted at a vertex or an edge of a graph whose order is close to the Moore bound. This approach has already been successfully used for estimates of the orders of the extremal vertex-transitive graphs, for which it had been shown that for every constant c, there exist vertex-transitive extremal graphs whose orders differ from the Moore bound by more than c.
Primary author
Prof.
Robert Jajcay
(Comenius University and University of Primorska)
