标题： 关于西蒙和苏利文的第二邻域猜想 显示英文标题

标题： On Seymour's and Sullivan's Second Neighbourhood Conjectures

摘要： 对于有向图的一个顶点$x$，$d^+(x)$（$d^-(x)$，分别）是从（到，分别）$x$距离为 1 的顶点数量，而$d^{++}(x)$是从$x$距离为 2 的顶点数量。 1995年，Seymour猜想，对于任何有向图$D$，存在一个顶点$x$，使得$d^+(x)\leq d^{++}(x)$。 2006年，Sullivan猜想，在$D$中存在一个顶点$x$，使得$d^-(x)\leq d^{++}(x)$。 我们给出了一个充分条件，以三角形的数量来表示有向图满足Sullivan猜想。 特别是，这表明Sullivan猜想对平面图和无三角形图的所有定向都成立。 有向图$D$是一个有向分割图，如果$D$的顶点可以划分为顶点集$X$和$Y$，使得$X$是一个独立集，而$Y$诱导出一个竞赛图。 我们还证明了这两个猜想对于一些有向分割图族成立，特别是当$Y$诱导出一个正则或几乎正则的竞赛图时。 显示英文摘要

摘要： For a vertex $x$ of a digraph, $d^+(x)$ ($d^-(x)$, resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++}(x)$ is the number of vertices at distance 2 from $x$. In 1995, Seymour conjectured that for any oriented graph $D$ there exists a vertex $x$ such that $d^+(x)\leq d^{++}(x)$. In 2006, Sullivan conjectured that there exists a vertex $x$ in $D$ such that $d^-(x)\leq 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 of triangle-free graphs. An oriented graph $D$ is an oriented split graph if the vertices of $D$ can be partitioned into vertex sets $X$ and $Y$ such that $X$ is an independent set and $Y$ induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when $Y$ induces a regular or an almost regular tournament.