Vol. 2, No. 4, 2009

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
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

Let D be a simple digraph without loops or digons. For any v V (D) let N1(v) be the set of all nodes at out-distance 1 from v and let N2(v) 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 V (D) such that |N1(v)||N2(v)|. 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.

graph theory, second neigbhorhood conjecture, graph properties, open problems in graph theory
Mathematical Subject Classification 2000
Primary: 05C20
Received: 18 August 2008
Revised: 3 August 2009
Accepted: 13 August 2009
Published: 28 October 2009

Communicated by Vadim Ponomarenko
James Brantner
Department of Philosophy
Brandeis University
415 South Street
Waltham, MA 02453
United States
Greg Brockman
Department of Mathematics
Harvard University
1 Oxford Street
Cambridge, MA 02138
United States
Bill Kay
Department of Mathematics
University of South Carolina
Leconte 411
Columbia, SC 29208
United States
Emma Snively
Department of Mathematics
Rose–Hulman Institute of Technology
5500 Wabash Avenue
Terre Haute, IN 47803
United States