Document Type
Lecture
Publication Date
11-6-2024
Abstract
Anundirected Moore graph has the maximum number of vertices possible among all graphs with given maximum valency and diameter. It was shown by Bannai and Ito, and Damerell that a non-complete Moore graph must be regular of valency 2, 3, 7, or 57, where the existence of a graph in the latter case is a famous open problem in algebraic graph theory. We consider a generalization of Moore graphs to digraphs (or mixed graphs), where both undirected edges and arcs are allowed. It was shown by Nguyen, Miller, and Gimbert that the diameter of a Moore digraph is at most 2, but unlike the undirected Moore graphs, there are an infinite number of feasible (in-, out-) valencies. However, only three Moore digraphs are known: the Bos´ak graph on 18 vertices, and the two Jørgensen graphs on 108 vertices. Furthermore, these three are Cayley graphs and therefore it may make sense to search for more examples of Moore digraphs among Cayley graphs. Using an observation of G. Higman from the theory of association schemes, also known as Benson’s lemma in finite geometry, we show non-existence of Moore Cayley digraphs of certain small orders.
Relational Format
presentation
Recommended Citation
Gavrilyuk, Alexander, "On the non-existence of some Moore Cayley digraphs" (2024). Combinatorics Seminar. 4.
https://egrove.olemiss.edu/math_combinatorics/4
