Vol. 2, No. 4, 2009

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

Volume 10
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
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
Abstract

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.

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

Communicated by Vadim Ponomarenko
Authors
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