Vol. 2, No. 4, 2009

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

Volume 11
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179

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’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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