Extremal digraphs avoiding distinct walks of length 3 with the same endpoints

2021/04/17 by Huang, Zejun, Lyu, Zhenhua · 1 citation
#05C20 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.08498

Abstract

In this paper, we determine the maximum size of digraphs on n vertices in which there are no two distinct walks of length 3 with the same initial vertex and the same terminal vertex. The digraphs attaining this maximum size are also characterized. Combining this with previous results, we obtain a full solution to a problem proposed by X. Zhan in 2007.

Cited by

• New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems

Related

• A note on extremal digraphs containing at most t walks of length k with the same endpoints
• Turán problems for digraphs avoiding distinct walks of a given length with the same endpoints
• Extremal digraphs containing at most t paths of length 2 with the same endpoints
• Extremal digraphs avoiding an orientation of C₄
• Digraphs with a fixed number of edges and vertices, having a maximal number of walks of length 2