On Seymour's second neighborhood conjecture of \(m\)-free digraphs

DOI10.1016/J.DISC.2017.04.003zbMath1362.05053arXiv1701.00328OpenAlexW2568657929WikidataQ123189534 ScholiaQ123189534MaRDI QIDQ2397537

Hao Liang, Jun-Ming Xu

Publication date: 22 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper gives an approximate result related to Seymour's Second Neighborhood conjecture, that is, for any $m$-free digraph $G$, there exists a vertex $vin V(G)$ and a real number $lambda_m$ such that $d^{++}(v)geq lambda_m d^+(v)$, and $lambda_m ightarrow 1$ while $m ightarrow +infty$. This result generalizes and improves some known results in a sense.

Full work available at URL: https://arxiv.org/abs/1701.00328

zbMATH Keywords

digraphdirected cycleSeymour's second neighborhood conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Cites Work

• The number of Seymour vertices in random tournaments and digraphs
• On directed triangles in digraphs
• Second neighborhood via first neighborhood in digraphs
• Minimum feedback arc set of \(m\)-free digraphs
• On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
• Remarks on the second neighborhood problem
• On Iterated Image Size for Point-Symmetric Relations
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (4)

Unnamed Item ⋮ 4-Free Strong Digraphs with the Maximum Size ⋮ Seymour's second neighborhood conjecture for 5-anti-transitive oriented graphs ⋮ Seymour's second neighborhood conjecture for \(m\)-free, \(k\)-transitive, \(k\)-anti-transitive digraphs and some approaches

This page was built for publication: On Seymour's second neighborhood conjecture of \(m\)-free digraphs