On the existence of \((d,k)\)-digraphs (Q1292845)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the existence of \((d,k)\)-digraphs
scientific article

    Statements

    On the existence of \((d,k)\)-digraphs (English)
    0 references
    0 references
    5 December 1999
    0 references
    A \((d,k)\)-digraph \(G\) is a regular digraph of degree \(d\geq 2\), diameter \(k\geq 2\) and order \(d+d^2+\cdots +d^k\) (i.e. one less than the Moore bound). There are several necessary conditions for the existence of such digraphs based on the so-called repeat permutation \(P\); see, e.g., \textit{E. T. Baskoro, M. Miller, J. Plesník}, and \textit{S. Znám} [J. Graph Theory 20, No. 3, 339-349 (1995; Zbl 0838.05054)] and \textit{E. T. Baskoro, M. Miller}, and \textit{J. Plesník} [Graphs Comb. 14, No. 2, 109-119 (1998; Zbl 0905.05033)]. The author derives several relationships between the spectrum of \(G\) and the cycle structure of \(P\) to obtain new necessary conditions. In particular, it is shown that there is exactly one \((4,2)\)-digraph, namely the line digraph of the complete digraph on 5 vertices.
    0 references
    digraph
    0 references
    degree
    0 references
    diameter
    0 references
    Moore bound
    0 references
    spectrum
    0 references
    almost Moore digraph
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references