Digraphs that contain at most t distinct walks of a given length with the same endpoints

Zhenhua Lyu ()
Additional contact information
Zhenhua Lyu: School of Science, Shenyang Aerospace University

Journal of Combinatorial Optimization, 2021, vol. 41, issue 3, No 9, 762-779

Abstract: 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? Determine the extremal digraphs attaining the maximum number. When $$t=1$$ t = 1 , the problem has been studied by Wu, by Huang and Zhan, by Huang, Lyu and Qiao, by Lyu in four papers, and they solved all the cases but $$k=3$$ k = 3 . For $$t\ge 2$$ t ≥ 2 , Huang and Lyu proved that the maximum number is equal to $$n(n-1)/2$$ n ( n - 1 ) / 2 and the extremal digraph is the transitive tournament when $$n\ge 6t+2$$ n ≥ 6 t + 2 and $$k\ge n-1$$ k ≥ n - 1 . They also discussed the maximum number for the case $$n=k+2,k+3,k+4$$ n = k + 2 , k + 3 , k + 4 . In this paper, we solve the problem for the case $$k\ge 6t+1$$ k ≥ 6 t + 1 and $$n\ge k+5$$ n ≥ k + 5 , and we also characterize the structures of the extremal digraphs for $$n=k+2,k+3,k+4$$ n = k + 2 , k + 3 , k + 4 .

Keywords: Turán problem; Digraph; Walk; Tournament; 05C35; 05C20 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00718-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:3:d:10.1007_s10878-021-00718-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00718-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().