On Seymour's and Sullivan's second neighbourhood conjectures
On Seymour's and Sullivan's second neighbourhood conjectures
复制标题
关于西摩和沙利文的第二邻域猜想
DOI：
10.1002/jgt.23050
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
Ai J
中科院分区：
文献类型：
--
作者：
Ai J
For a vertex x $x$ of a digraph, d + ( x ) ${d}^{+}(x)$ (d − ( x ) ${d}^{-}(x)$, respectively) is the number of vertices at distance 1 from (to, respectively) x $x$ and d + + ( x ) ${d}^{++}(x)$ is the number of vertices at distance 2 from x $x$. In 1995, Seymour conjectured that for any oriented graph D $D$ there exists a vertex x $x$ such that d + ( x ) ≤ d + + ( x ) ${d}^{+}(x)\le {d}^{++}(x)$. In 2006, Sullivan conjectured that there exists a vertex x $x$ in D $D$ such that d − ( x ) ≤ d + + ( x ) ${d}^{-}(x)\le {d}^{++}(x)$. We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and triangle‐free graphs. An oriented graph D $D$ is an oriented split graph if the vertices of D $D$ can be partitioned into vertex sets X $X$ and Y $Y$ such that X $X$ is an independent set and Y $Y$ induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when Y $Y$ induces a regular or an almost regular tournament.
For a vertex x $x$ of a digraph, d + ( x ) ${d}^{+}(x)$ (d − ( x ) ${d}^{-}(x)$, respectively) is the number of vertices at distance 1 from (to, respectively) x $x$ and d + + ( x ) ${d}^{++}(x)$ is the number of vertices at distance 2 from x $x$. In 1995, Seymour conjectured that for any oriented graph D $D$ there exists a vertex x $x$ such that d + ( x ) ≤ d + + ( x ) ${d}^{+}(x)\le {d}^{++}(x)$. In 2006, Sullivan conjectured that there exists a vertex x $x$ in D $D$ such that d − ( x ) ≤ d + + ( x ) ${d}^{-}(x)\le {d}^{++}(x)$. We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and triangle‐free graphs. An oriented graph D $D$ is an oriented split graph if the vertices of D $D$ can be partitioned into vertex sets X $X$ and Y $Y$ such that X $X$ is an independent set and Y $Y$ induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when Y $Y$ induces a regular or an almost regular tournament.
关于具有几乎最优连通性的正则有向图的 Seymour 第二邻域猜想
DOI：
--
发表时间：
2013
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
A. Lladó
通讯作者：
A. Lladó