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