Turán Problems for k -Geodetic Digraphs

Tuite, James; Erskine, Grahame and Salia, Nika (2023). Turán Problems for k -Geodetic Digraphs. Graphs and Combinatorics, 39(2), article no. 25.

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

Metrics

Item Actions

Export

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

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
• • http://creativecommons.org/licenses/by/4...
• SWORD Depositor
• Jisc Publications-Router
• Depositing User
• Jisc Publications-Router