A Contribution to the Second Neighborhood Problem |
| |
Authors: | Salman Ghazal |
| |
Institution: | 1. Department of Mathematics, Faculty of Sciences I, Lebanese University, Hadath, Beirut, Lebanon 2. Département de Mathématiques, Institute Camille Jordan, Université Claude Bernard Lyon 1, 43 boulevard du 11 novembre 1918, 69622, Villeurbanne Cedex, France
|
| |
Abstract: | Seymour’s Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We prove this conjecture for classes of oriented graphs whose missing graph is a comb, a complete graph minus two independent edges, or a cycle of length 5. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|