#### Vol. 2, No. 4, 2009

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Contributions to Seymour's second neighborhood conjecture

### James Brantner, Greg Brockman, Bill Kay and Emma Snively

Vol. 2 (2009), No. 4, 387–395
##### Abstract

Let $D$ be a simple digraph without loops or digons. For any $v\in V\left(D\right)$ let ${N}_{1}\left(v\right)$ be the set of all nodes at out-distance 1 from $v$ and let ${N}_{2}\left(v\right)$ be the set of all nodes at out-distance 2. We show that if the underlying graph is triangle-free, there must exist some $v\in V\left(D\right)$ such that $|{N}_{1}\left(v\right)|\le |{N}_{2}\left(v\right)|$. We provide several properties a “minimal” graph which does not contain such a node must have. Moreover, we show that if one such graph exists, then there exist infinitely many.

##### Keywords
graph theory, second neigbhorhood conjecture, graph properties, open problems in graph theory
Primary: 05C20