A note on extremal digraphs containing at most t walks of length k with the same endpoints

2021/06/01 by Lyu, Zhenhua
#05C20 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.00212

Abstract

Let n,k,t be positive integers. What is the maximum number of arcs in a digraph on n vertices in which there are at most t distinct walks of length k with the same endpoints? In this paper, we prove that the maximum number is equal to n(n-1)/2 and the extremal digraph are the transitive tournaments when k≥ n-1≥ max\2t+1,2\lceil √(2t+9/4)+1/2\rceil+3\. Based on this result, we may determine the maximum numbers and the extremal digraphs for k≥ max\2t+1,2\lceil √(2t+9/4)+1/2\rceil+3\ and n is sufficiently large, which generalises the existing results. A conjecture is also presented.

Related

• Extremal digraphs avoiding distinct walks of length 3 with the same endpoints
• Extremal digraphs containing at most t paths of length 2 with the same endpoints
• Turán problems for digraphs avoiding distinct walks of a given length with the same endpoints
• Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2
• The Turan problems of directed paths and cycles in digraphs