An Extension of Seymour’s Second Neighborhood Conjecture
摘要
Seymour’s second neighborhood conjecture states that every directed graph with no symmetric arcs has a vertex v such that the second neighborhood of v is at least as large as the first neighborhood of v. This has been proven for a variety of classes of directed graphs but not in general. We propose a similar conjecture comparing first neighborhoods to third neighborhoods. We find some classes of graphs which satisfy this new conjecture.