A note on the second neighborhood problem for $k$-anti-transitive and $m$-free digraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917677157580800 |
|---|---|
| author | Mezher, Dania Daamouch, Moussa |
| author_facet | Mezher, Dania Daamouch, Moussa |
| contents | Seymour Second Neighborhood Conjecture (SSNC) asserts that every finite oriented graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. A digraph $D = (V, E)$ is $k$-anti-transitive if for every pair of vertices $u, v \in V$, the existence of a directed path of length $k$ from $u$ to $v$ implies that $(u, v) \notin E$. An $m$-free digraph is digraph having no directed cycles with length at most $m$. In this paper, we prove that if $D$ is $k$-anti-transitive and $(k-4)$-free digraph, then $D$ has a Seymour vertex. As a consequence, a special case of Caccetta-Haggkvist Conjecture holds on 7-anti-transitive oriented graphs. This work extends recently known results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17797 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on the second neighborhood problem for $k$-anti-transitive and $m$-free digraphs Mezher, Dania Daamouch, Moussa Combinatorics 05C20 Seymour Second Neighborhood Conjecture (SSNC) asserts that every finite oriented graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. A digraph $D = (V, E)$ is $k$-anti-transitive if for every pair of vertices $u, v \in V$, the existence of a directed path of length $k$ from $u$ to $v$ implies that $(u, v) \notin E$. An $m$-free digraph is digraph having no directed cycles with length at most $m$. In this paper, we prove that if $D$ is $k$-anti-transitive and $(k-4)$-free digraph, then $D$ has a Seymour vertex. As a consequence, a special case of Caccetta-Haggkvist Conjecture holds on 7-anti-transitive oriented graphs. This work extends recently known results. |
| title | A note on the second neighborhood problem for $k$-anti-transitive and $m$-free digraphs |
| topic | Combinatorics 05C20 |
| url | https://arxiv.org/abs/2405.17797 |