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.

DOI: https://doi.org/10.1007/978-3-030-83823-2_124

Abstract

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

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI