The structure of digraphs with excess one

DOI10.1002/JGT.23082MaRDI QIDQ6378935zbMATH OpenOpenAlexFDO

Authors James Tuite

Publication date 29 September 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/jgt.23082

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: A digraph $G$ is emph{$k$-geodetic} if for any (not necessarily distinct) vertices $u,v$ there is at most one directed walk from $u$ to $v$ with length not exceeding $k$. The order of a $k$-geodetic digraph with minimum out-degree $d$ is bounded below by the directed Moore bound $M(d,k)=1+d+d^2+dots+d^k$. The Moore bound can be met only in the trivial cases $d=1$ and $k=1$, so it is of interest to look for $k$-geodetic digraphs with out-degree $d$ and smallest possible order $M(d,k)+epsilon$, where $epsilon$ is the emph{excess} of the digraph. Miller, Miret and Sillasen recently ruled out the existence of digraphs with excess one for $k=3,4$ and $dgeq2$ and for $k=2$ and $dgeq8$. We conjecture that there are no digraphs with excess one for $d,kgeq2$ and in this paper we investigate the structure of minimal counterexamples to this conjecture. We severely constrain the possible structures of the outlier function and prove the non-existence of certain digraphs with degree three and excess one, as well closing the open cases $k=2$ and $d=3,4,5,6,7$ left by the analysis of Miller et al. We further show that there are no involutary digraphs with excess one, i.e. the outlier function of any such digraph must contain a cycle of length $geq3$.

Recommendations

• On digraphs of excess one
• On k-geodetic digraphs with excess one
• On diregular digraphs with degree two and excess three
• Digraphs with degree two and excess two are diregular
• On diregular digraphs with degree two and excess two

Cited in

(1)

• New results regarding the permutation cycle structure of almost Moore digraphs

This page was built for publication: The structure of digraphs with excess one

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