Seymour's second neighbourhood conjecture for quasi-transitive oriented graphs
classification
💻 cs.DM
math.CO
keywords
conjectureorientedquasi-transitivesecondeverygraphsneighbourhoodout-neighbourhood
read the original abstract
Seymour's second neighbourhood conjecture asserts that every oriented graph has a vertex whose second out-neighbourhood is at least as large as its out-neighbourhood. In this paper, we prove that the conjecture holds for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. A digraph $D$ is called quasi-transitive is for every pair $xy,yz$ of arcs between distinct vertices $x,y,z$, $xz$ or $zx$ ("or" is inclusive here) is in $D$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.