On the existence of (d,k)-digraphs

DOI10.1016/S0012-365X(99)90087-0MaRDI QIDQ1292845zbMATH OpenOpenAlexFDO

Authors Joan Gimbert

Publication date 5 December 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)90087-0

zbMATH Keywords

almost Moore digraphdegreediameterdigraphMoore boundspectrum

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

• Combinatorial Geometry and Graph Theory
• On the structure of digraphs with order close to the Moore bound
• Structure of repeat cycles in almost Moore digrpahs with selfrepeats and diameter 3
• On (4, 2)-digraphs containing a cycle of length 2

Cites work

• Digraphs of degree 3 and order close to the moore bound
• scientific article; zbMATH DE number 426169 (Why is no real title available?)
• scientific article; zbMATH DE number 51347 (Why is no real title available?)
• scientific article; zbMATH DE number 3455291 (Why is no real title available?)
• scientific article; zbMATH DE number 3588689 (Why is no real title available?)
• scientific article; zbMATH DE number 637285 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1792622 (Why is no real title available?)
• scientific article; zbMATH DE number 3218572 (Why is no real title available?)
• scientific article; zbMATH DE number 3319714 (Why is no real title available?)
• Line Digraph Iterations and the (d, k) Digraph Problem
• Minimum Diameter of Diregular Digraphs of Degree 2
• On the impossibility of directed Moore graphs
• On the structure of digraphs with order close to the Moore bound

Cited in

(18)

• On the contractibility of a digraph onto \(K_ 4^*\)
• On digraphs of excess one
• On the non-existence of families of \((d,k, \delta)\)-digraphs containing only selfrepeat vertices
• k-distinct in- and out-branchings in digraphs
• On diregular digraphs with degree two and excess three
• On the nonexistence of almost Moore digraphs
• Enumerations of vertex orders of almost Moore digraphs with selfrepeats
• On the nonexistence of almost Moore digraphs of degree four and five
• Nonexistence of almost Moore digraphs of degrees 4 and 5 with self-repeats
• A note on constructing digraphs with prescribed properties
• scientific article; zbMATH DE number 5016654 (Why is no real title available?)
• On \(d\)-Fibonacci digraphs
• Combinatorial Geometry and Graph Theory
• On (4, 2)-digraphs containing a cycle of length 2
• New results regarding the permutation cycle structure of almost Moore digraphs
• On the nonexistence of almost Moore digraphs with self-repeats
• Multipartite Moore digraphs
• On mixed Moore graphs

This page was built for publication: On the existence of \((d,k)\)-digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1292845)