Turan problems for k-geodetic digraphs

DOI10.1007/S00373-023-02619-XMaRDI QIDQ6360228arXivFDO

Authors James Tuite, Grahame Erskine, Nika Salia

Publication date 9 February 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00373-023-02619-X

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Connectivity (05C40)

arXiv classification

math.CO

Abstract: A digraph $G$ is emph{$k$-geodetic} if for any pair of (not necessarily distinct) vertices $u,vinV(G)$ there is at most one walk of length $leqk$ from $u$ to $v$ in $G$. In this paper we determine the largest possible size of a $k$-geodetic digraph with given order. We then consider the more difficult problem of the largest size of a strongly-connected $k$-geodetic digraph with given order, solving this problem for $k=2$ and giving a construction which we conjecture to be extremal for larger $k$. We close with some results on generalised Tur'{a}n problems for the number of directed cycles and paths in $k$-geodetic digraphs.

This page was built for publication: Turan problems for $k$-geodetic digraphs

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