Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.16101 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910503668809728 |
|---|---|
| author | Huang, Zejun Lyu, Zhenhua |
| author_facet | Huang, Zejun Lyu, Zhenhua |
| contents | Given a positive integer $t$, let $P_{t,2}$ be the digraph consisting of $t$ directed paths of length 2 with the same initial and terminal vertices. In this paper, we study the maximum size of $P_{t+1,2}$-free digraphs of order $n$, which is denoted by $ex(n, P_{t+1,2})$. For sufficiently large $n$, we prove that $ex(n, P_{t+1})=g(n,t)$ when $\lfloor(n-t)/{2} \rfloor$ is odd and $ex(n, P_{t+1,2})\in \{g(n,t)-1, g(n,t)\}$ when $\lfloor(n-t)/{2} \rfloor$ is even, where $g(n,t)=\left\lceil(n+t)/{2}\right\rceil \left\lfloor(n-t)/{2}\right\rfloor+tn+1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16101 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal digraphs containing at most $t$ paths of length 2 with the same endpoints Huang, Zejun Lyu, Zhenhua Combinatorics Given a positive integer $t$, let $P_{t,2}$ be the digraph consisting of $t$ directed paths of length 2 with the same initial and terminal vertices. In this paper, we study the maximum size of $P_{t+1,2}$-free digraphs of order $n$, which is denoted by $ex(n, P_{t+1,2})$. For sufficiently large $n$, we prove that $ex(n, P_{t+1})=g(n,t)$ when $\lfloor(n-t)/{2} \rfloor$ is odd and $ex(n, P_{t+1,2})\in \{g(n,t)-1, g(n,t)\}$ when $\lfloor(n-t)/{2} \rfloor$ is even, where $g(n,t)=\left\lceil(n+t)/{2}\right\rceil \left\lfloor(n-t)/{2}\right\rfloor+tn+1$. |
| title | Extremal digraphs containing at most $t$ paths of length 2 with the same endpoints |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.16101 |