New Bounds on k-Geodetic Digraphs and Mixed Graphs

Tuite, James and Erskine, Grahame (2021). New Bounds on k-Geodetic Digraphs and Mixed Graphs. In: Extended Abstracts EuroComb 2021 (Nešetřil, Jaroslav; Perarnau, Guillem; Rué, Juanjo and Serra, Oriol eds.), pp. 778–783.



We study a generalisation of the degree/girth problem to the setting of directed and mixed graphs. We say that a mixed graph or digraph G is k-geodetic if there is no pair of vertices u, v such that G contains distinct non-backtracking walks of length ≤ k from u to v. The order of a k-geodetic mixed graph with minimum undirected degree r and minimum directed out-degree z in general exceeds the mixed Moore bound M(r, z, k) by some small excess ϵ. Bannai and Ito proved that there are no non-trivial undirected graphs with excess one. In this paper we investigate the structure of digraphs with excess one and derive results on the permutation structure of the outlier function that rules out the existence of certain digraphs with excess one. We also present strong bounds on the excess of k-geodetic mixed graphs and show that there are no k-geodetic mixed graphs with excess one for k ≥ 3 .

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions