pith. sign in

arxiv: 1704.01389 · v2 · pith:RYGIDNTLnew · submitted 2017-04-05 · 💻 cs.DM · math.CO

Seymour's second neighbourhood conjecture for quasi-transitive oriented graphs

classification 💻 cs.DM math.CO
keywords conjectureorientedquasi-transitivesecondeverygraphsneighbourhoodout-neighbourhood
0
0 comments X
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.