Premium
Complete characterization of almost Moore digraphs of degree three
Author(s) -
Baskoro Edy Tri,
Miller Mirka,
Širáň Jozef,
Sutton Martin
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20042
Subject(s) - mathematics , degree (music) , combinatorics , characterization (materials science) , upper and lower bounds , graph , discrete mathematics , graph theory , digraph , mathematical analysis , materials science , physics , acoustics , nanotechnology
It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005