A Note on Moore Cayley Digraphs

Let Δ be a digraph of diameter 2 with the maximum undirected vertex degree t and the maximum directed out-degree z . The largest possible number v of vertices of Δ is given by the following generalization of the Moore bound: v ≤ ( z + t ) 2 + z + 1 , and a digraph attaining this bound is called a Mo...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021-09, Vol.37 (5), p.1509-1520
Main Authors: Gavrilyuk, Alexander L., Hirasaka, Mitsugu, Kabanov, Vladislav
Format: Article
Language:English
Subjects:
Apexes
Combinatorics
Engineering Design
Graph theory
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let Δ be a digraph of diameter 2 with the maximum undirected vertex degree t and the maximum directed out-degree z . The largest possible number v of vertices of Δ is given by the following generalization of the Moore bound: v ≤ ( z + t ) 2 + z + 1 , and a digraph attaining this bound is called a Moore digraph. Apart from the case t = 1 , only three Moore digraphs are known, which are also Cayley graphs. Using computer search, Erskine (J Interconnect Netw, 17: 1741010, 2017) ruled out the existence of further examples of Cayley digraphs attaining the Moore bound for all orders up to 485. We use an algebraic approach to this problem, which goes back to an idea of G. Higman from the theory of association schemes, also known as Benson’s Lemma in finite geometry, and show non-existence of Moore Cayley digraphs of certain orders.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-021-02286-w