Copy the page URI to the clipboard
Tuite, James; Erskine, Grahame and Salia, Nika
(2023).
DOI: https://doi.org/10.1007/s00373-023-02619-x
Abstract
A digraph G is k-geodetic if for any pair of (not necessarily distinct) vertices u, v∈V(G) there is at most one walk of length ≤k from u to v in G. In this paper, we determine the largest possible size of a k-geodetic digraph with a given order. We then consider the more difficult problem of the largest size of a strongly-connected k-geodetic digraph with a 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án problems for the number of directed cycles and paths in k-geodetic digraphs.
Viewing alternatives
Download history
Metrics
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from DimensionsItem Actions
Export
About
- Item ORO ID
- 87574
- Item Type
- Journal Item
- ISSN
- 1435-5914
- Project Funding Details
-
Funded Project Name Project ID Funding Body Not Set EP/W522338/1 EPSRC (Engineering and Physical Sciences Research Council) Not Set ECF-2021-27 London Mathematical Society (LMS) - Keywords
- Digraph; Turán Problem; Extremal; k-geodetic; Strong-connectivity
- Academic Unit or School
-
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM) - Copyright Holders
- © 2023 The Authors
- Related URLs
- SWORD Depositor
- Jisc Publications-Router
- Depositing User
- Jisc Publications-Router