Seymour’s Second Neighborhood Conjecture for 6-antitransitive digraphs
| Autor: | Mehvish I. Poshni, Mudassir Shabbir, Imran F. Khan, Zohair Raza Hassan |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Vertex (graph theory)
Mathematics::Combinatorics Conjecture Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning Digraph 0102 computer and information sciences 02 engineering and technology 01 natural sciences Longest path problem Combinatorics Cardinality Computer Science::Discrete Mathematics 010201 computation theory & mathematics Simple (abstract algebra) Path (graph theory) Discrete Mathematics and Combinatorics Antitransitive Mathematics |
| Zdroj: | Discrete Applied Mathematics. 292:59-63 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.12.026 |
| Popis: | Seymour’s Second Neighborhood Conjecture states that every simple oriented graph has a vertex such that the cardinality of its second neighborhood is greater than or equal to the cardinality of its first neighborhood. The conjecture has been shown to hold for various families of digraphs but remains unsettled. A digraph is said to be k -antitransitive if any u to v path of length k implies there is no u to v edge. If the conjecture is shown to hold for k -antitransitive digraphs for an arbitrary k , this would settle it for finite digraphs, as every finite digraph is k -antitransitive for k greater than the length of its longest path. So far, the conjecture has been shown to hold for k -antitransitive simple oriented graphs for k ≤ 5 . In this paper we prove the conjecture for 6-antitransitive simple oriented graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect