Contributions to Seymour’s second neighborhood conjecture

Brantner, James; Brockman, Greg; Kay, Bill; Snively, Emma

doi:10.2140/involve.2009.2.387

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

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

DOI: 10.2140/involve.2009.2.387

Abstract

Let $D$ be a simple digraph without loops or digons. For any $v \in V (D)$ let $N_{1} (v)$ be the set of all nodes at out-distance 1 from $v$ and let $N_{2} (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 \in V (D)$ such that $| N_{1} (v) | \leq | N_{2} (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

Vol. 2, No. 4, 2009