Graphs of order two less than the Moore bound (Q924968)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs of order two less than the Moore bound |
scientific article |
Statements
Graphs of order two less than the Moore bound (English)
0 references
29 May 2008
0 references
The degree/diameter problem asks to determine the largest order \(n_{d,k}\) of a graph of maximum degree at most \(d\) and diameter at most \(k\). It is well known that for \(d\geq 3\) and \(k\geq 3\) the known Moore bound \(M_{d,k}=1+d+d(d-1)+\cdots +d(d-1)^{k-1}\) cannot be attained. In this paper graphs of order \(M_{d,k}- 2\) are studied. The results make use of the notion of a repeat. The main result says that if \(d=4\) and \(k\geq 3\) then there are no such graphs.
0 references
degree/diameter problem
0 references
Moore bound
0 references
repeat
0 references