A note on extremal digraphs containing at most $t$ walks of length $k$ with the same endpoints
| Autor: | Lyu, Zhenhua |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\ge n-1\ge \max\{2t+1,2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil+3\}$. Based on this result, we may determine the maximum numbers and the extremal digraphs for $k\ge \max\{2t+1,2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil+3\}$ and $n$ is sufficiently large, which generalises the existing results. A conjecture is also presented. Comment: 7 pages, 0 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|