Turan problems for $k$-geodetic digraphs
Preprint
Abstract
A digraph $G$ is \emph{$k$-geodetic} if for any pair of (not necessarily distinct) vertices $u,v \in V(G)$ there is at most one walk of length $\leq k$ 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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Extremal digraphs avoiding distinct walks of length 3 with the same endpointsDiscrete Mathematics, 2022
- On diregular digraphs with degree two and excess twoDiscrete Applied Mathematics, 2018
- Many T copies in H-free graphsJournal of Combinatorial Theory, Series B, 2016
- On the maximum number of five-cycles in a triangle-free graphJournal of Combinatorial Theory, Series B, 2012
- The Maximum Number of Triangles in C2k+1-Free GraphsCombinatorics, Probability and Computing, 2012
- On the 0–1 matrices whose squares are 0–1 matricesLinear Algebra and its Applications, 2010
- Pentagons vs. trianglesDiscrete Mathematics, 2008
- Digraphs on permutationsDiscrete Mathematics, 1997
- Explicit construction of graphs with an arbitrary large girth and of large sizeDiscrete Applied Mathematics, 1995
- Girth in digraphsJournal of Graph Theory, 1980