arXiv
Open Access
2016
The Second Neighborhood Conjecture for Oriented Graphs Missing Combs
Salman Ghazal
Abstrak
Seymour's Second Neighborhood Conjecture asserts that every oriented graph has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Combs are the graphs having no induced $C_4$, $\overline{C_4}$, $C_5$, chair or $\overline{chair}$. We characterize combs using dependency digraphs. We characterize the graphs having no induced $C_4$, $\overline{C_4}$, chair or $\overline{chair}$ using dependency digraphs. Then we prove that every oriented graph missing a comb satisfies this conjecture. We then deduce that every oriented comb and every oriented threshold graph satisfies Seymour's conjecture.
Topik & Kata Kunci
Penulis (1)
S
Salman Ghazal
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2016
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓