Seymour's Second Neighborhood Conjecture for Tournaments Missing a Generalized Star

✍ Scribed by Salman Ghazal

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 90 KB
• Volume: 71
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20634

✦ Synopsis

Abstract

Seymour's Second Neighborhood Conjecture asserts that every digraph (without digons) has a vertex whose first out‐neighborhood is at most as large as its second out‐neighborhood. We prove its weighted version for tournaments missing a generalized star. As a consequence the weighted version holds for tournaments missing a sun, star, or a complete graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:89–94, 2012