Seymour’s Second Neighborhood Conjecture (SSNC) asserts that every finite oriented graph has a vertex \(v\) whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. In this note, we introduce pseudo-Seymour set such that Seymour’s conjecture becomes: Every oriented graph has a singleton pseudo-Seymour set. We prove that any oriented graph has a pseudo-Seymour set \(S\) with \(|S|=2\). Furthermore, we show that there are pseudo-Seymour sets of any size at least 2. We define \(\rho\)-Seymour vertex where \(0 < \rho \leq 1\), and give an approach such that finding \(\rho=1\) is equivalent to the existence of Seymour vertex. Attempting to maximize its value, we prove that for any oriented graph with minimum out-degree \(\delta\), there is \(\rho=\frac{2}{3}(1+\frac{1}{2\delta})\).
A digraph \(D\) consists of a
non-empty finite set \(V(D)\) of
elements called vertices and a finite set \(E(D)\) of ordered pairs of distinct
vertices called arcs or directed edges. We call \(V(D)\) the vertex set and \(E(D)\) the arc set of \(D\). We will often write \(D = (V,E)\), which means that \(V\) and \(E\) are the vertex set and arc set of \(D\), respectively. In this note, a digraph
means an oriented graph; that is a digraph with no symmetric arcs.
We may write \(u \rightarrow v\) and we
say that \(u\) dominates \(v\), meaning that \((u,v) \in E(D)\). A directed path
on \(k\) vertices, denoted by \(P_k\), is a sequence of \(k\) distinct vertices \(x_1 x_2 \cdots x_k\) such that \(x_1 \rightarrow x_2 \rightarrow \cdots \rightarrow
x_k\) and \(P_k\) is referred to
as a directed path from \(x_1\) to
\(x_k\) or a directed \(x_1 x_k\)-path.
The length of a directed path is the number of its arcs.
The distance from a vertex \(x\) to another vertex \(y\) is the length of a shortest directed path from \(x\) to \(y\).
For a vertex \(v \in V(D)\):
\(\bullet\) The out-neighborhood, denoted \(N_D^+(v)\), is the set of all vertices at distance 1 from \(v\).
\(\bullet\) The second out-neighborhood of \(v\), denoted \(N_D^{++}(v)\), is the set of all vertices at distance 2 from \(v\).
\(\bullet\) The out-degree of \(v\) is \(d_D^+(v)=|N_D^+(v)|\) and its second out-degree is \(d_D^{++}(v)=|N_D^{++}(v)|\).
The minimum out-degree in \(D\) is denoted by \(\delta_D\).
For \(A \subseteq V(D)\), the subdigraph of \(D\) induced by \(A\) is denoted by \(D[A]\); where \(V(D[A])=A\) and for all \(u,v \in A\), we have \((u,v) \in E(D[A])\) if and only if \((u,v) \in E(D)\). We may write \(\overline{A}=V(D) \setminus A\) and \(N_A^+(v)= N_D^+(v) \cap A\) as well as \(d_A^+(v)=|N_A^+(v)|\). We define the out-neighborhood of \(A\) by \(N^+(A)=\cup_{x \in A}N^+(x) \setminus A\). It is easy to see that \(N_D^{++}(v) = N^+(N^+(v))\). We omit the subscript when it is clear from the context. We say that a vertex \(v\) is a Seymour vertex if \(|N^{++}(v)| \geq |N^+(v)|\).
In 1990, Paul Seymour proposed the following conjecture.
Conjecture 1.1 (SSNC) In every finite oriented graph, there exists a Seymour vertex.
Seymour’s Conjecture soon became an important topic of interest in graph theory. Although extensive research has been conducted, SSNC remains open, having been proven only for specific classes of oriented graphs.
The first significant breakthrough came in 1996 when Fisher [15] proved the conjecture for tournaments using probabilistic arguments and Farkas’s Lemma. Later, in 2000, Havet and Thomassé [23] provided a short proof for tournaments using median orders. They demonstrated that for tournaments, every feed vertex (the last vertex in a median order) is a Seymour vertex and showed that at least two Seymour vertices exist if no vertex is a sink (a vertex with out-degree zero).
Despite these advances, for general oriented graphs, a feed vertex is not necessarily a Seymour vertex. However, the completion approach, which involves extending an oriented graph into a tournament and leveraging median orders, has been employed to tackle several cases.
Fidler and Yuster [14] used median orders and dependency digraphs to prove SSNC for tournaments missing a matching. Ghazal extended these results, demonstrating SSNC for tournaments missing a generalized star [17] and tournaments missing a comb [18]. Building on these results, Al-Mniny and Ghazal [28] established SSNC for tournaments missing a generalized comb. Dara et al. [12] proved SSNC for tournaments missing both a matching and a star, thereby extending the results of Fidler, Yuster [14], and Ghazal [20].
Most of these results [28, 12, 14, 17, 18, 19, 20] were obtained using the completion approach.
Additionally, Ghazal [19] provided an alternative proof for SSNC on tournaments missing a matching using good digraphs. In 2016, he extended these results by proving SSNC for tournaments missing \(n\) disjoint stars under certain conditions [20].
Following these approaches, it is proved that SSNC holds for tournaments missing disjoint paths of length at most 2 under some conditions and for tournaments missing two stars without conditions [11].
In 2001, Kaneko and Locke [24] proved SSNC for every oriented graph with a minimum out-degree of at most 6 using combinatorial arguments. Their result implies that any counterexample to SSNC must have a minimum out-degree of at least 7. Further studies on potential counterexamples have been conducted by Brantner et al. [2], Zelenskiy [30], and Espuny Díaz et al. [13].
In 2003, Chen, Shen, and Yuster [5] introduced an approximation approach to SSNC by studying the maximum constant \(\lambda\) such that every oriented graph has a vertex \(v\) with:
\[d^{++}(v) \geq \lambda d^+(v).\]
They showed that \(\lambda = 0.657\cdots\), the unique real root of \(2x^3 + x^2 – 1 = 0\) in \((0, 1)\).
Later, Liang and Xu [25] improved this result for \(m\)-free digraphs (digraphs with no directed cycles of length at most \(m\)), proving that: \[d^{++}(v) \geq \lambda_m d^+(v), \text{ and } \lambda_m \to 1 \text{ as } m \to \infty,\] where \({\lambda}_m\) is the only real root in the interval \((0,1)\) of the polynomial \[g_m(x)=2x^3-(m-3)x^2+(2m-4)x-(m-1).\]
In 2013, Lladó [26] proved SSNC for regular oriented graphs with out-degree \(r\) and connectivity \(r-1\). In 2019, Cary [3] found Seymour vertices in certain Eulerian oriented graphs, specifically those admitting a simple cycle intersection graph. The conjecture remains open for general regular and Eulerian oriented graphs.
Cohn et al. [6] studied the number of Seymour vertices in random orientations of binomial random graphs \(G(n,p)\). In 2023, Botler, Moura, and Naia [1] proved that, asymptotically almost surely, every orientation of \(G(n, p)\) has a Seymour vertex whenever \(p < 1/4\). Espuny Díaz et al. [13] further improved this result, extending the range to \(p < 1/2\).
A digraph \(D\) is \(k\)-anti-transitive if the existence of a directed path of length \(k\) from \(u\) to \(v\) implies that \(u \nrightarrow v\). In other words, the class of \(k\)-anti-transitive digraphs are that of digraphs with forbidden \(C(k,1)\) where \(C(k,1)\) is the oriented cycle on \(k+1\) vertices obtained from the directed cycle on \(k+1\) vertices \(C_{k+1}\) by reversing the direction of exactly one arc. For example, 2-anti-transitive digraphs are oriented graphs with no transitive triangles.
It has been proved, in [7, 9], that SSNC holds for \(k\)-anti-transitive oriented graphs for \(k \in{ 3, 4, 5 }\) with at least two Seymour vertices for \(k \leq 4\) [9]. Furthermore, in 2021, Hassan et al. [22] extended this to 6-anti-transitive oriented graphs (with forbidden \(C(6,1)\)). In 2023, Chen and Chang [4] proved SSNC for graphs with forbidden \(C(6,2)\) (an oriented cycle obtained from \(C_8\) by reversing two consecutive arcs).
An oriented graph \(D\) is \(k\)–transitive if for every pair of vertices \(u\) and \(v\), any directed path from \(u\) to \(v\) of length \(k\) implies \(u \rightarrow v\). In terms of forbidden (not necessarily induced) subdigraphs, \(k\)-transitive oriented graphs are oriented graphs with forbidden \(P_{k+1}^*\) and \(C_{k+1}\), where \(P_{k+1}^*\) is a \(uv\)-path on \(k+1\) vertices such that \(u\) and \(v\) are not adjacent in \(D\). García-Vásquez and Hernández-Cruz [16] (2017) showed that every 4-transitive oriented graph has a Seymour vertex.
It is now established that SSNC holds for \(k\)-transitive oriented graphs for all \(k \leq 11\) [10], with at least two Seymour vertices for \(k \leq 6\) [9].
It has been proved that SSNC holds for \((\delta -1)\)-free digraphs, where \(\delta\) is the minimum out-degree [9]. Furthermore, combined results show SSNC for \(k\)-transitive oriented graphs that are \((\frac{k}{2}-1)\)-free [9] and for \(k\)-anti-transitive oriented graphs that are \((k-4)\)-free [27].
A digraph is \(k\)-quasi-transitive if every directed path of length \(k\) implies a direct arc between its endpoints. In terms of forbidden subdigraphs, \(k\)-quasi-transitive oriented graphs are oriented graphs with forbidden \(P_{k+1}^*\). Gutin and Li [21] (2017) proved SSNC for 2-quasi-transitive oriented graphs. Additionally, SSNC has been established for 3-quasi-transitive oriented graphs [8].
In this note, we introduce pseudo-Seymour sets such that the existence of a singleton pseudo-Seymour set is equivalent to the existence of a Seymour vertex, and we show that every oriented graph has a pseudo-Seymour set of size equals two. Also, we define \(\rho\)-Seymour vertex (\(0 < \rho \leq 1\)) such that the existence of \(\rho = 1\) implies the existence of a Seymour vertex. For any oriented graph, we prove that there exists \(\rho\)-Seymour vertex such that \(\rho=\frac{2}{3}(1+\frac{1}{2\delta})\).
Definition 2.1. Let \(D\) be a digraph and let \(S \subseteq V(D)\). A vertex \(v\) is called an ideal out-neighbor of \(S\) if \(v \in N^+(u)\) for all \(u \in S\).
We denote by \(N^\oplus(S)\) the set of all ideal out-neighbors of \(S\).
Definition 2.2. Let \(w \in V(D)\setminus N^\oplus(S)\). We say that \(w\) is a pseudo second out-neighbor of \(S\) if there exists \(u \in N^\oplus(S)\) such that \(u \rightarrow w\).
We denote by \(N^{\oplus \oplus}(S)\) the set of all pseudo second out-neighbors of \(S\).
It is easily seen that \(N^{\oplus \oplus}(S)=N^+(N^\oplus(S))\).
Definition 2.3. Let \(D\) be an oriented graph and let \(S \subseteq V(D)\). We say that \(S\) is a pseudo-Seymour set if \(|N^\oplus(S)| \leq |N^{\oplus \oplus}(S)|\).
Note that if \(S=\{v\}\), then \(N^\oplus(S)=N^+(v)\) and \(N^{\oplus \oplus}(S)=N^{++}(v)\). Hence, \(\{v\}\) is a singleton pseudo-Seymour set if and only if \(v\) is a Seymour vertex. SSNC can be restate as follows.
Conjecture 2.4. Every finite oriented graph has a singleton pseudo-Seymour set.
It is clear that every oriented graph \(D\) has a pseudo-Seymour set, for example, \(S=V(D)\) is a trivial pseudo Seymour set. Our objective is to find a pseudo-Seymour set with minimum size as possible.
Lemma 2.5. Let \(D\) be an oriented graph. If \(X \subseteq V(D)\), then \(|N^+(X)| \geq \delta – \frac{|X|-1}{2}\).
Proof. Let \(x \in X\) such that \(d_X^+(x)=\delta_{D[X]}\). It is easy to check that \(d_X^+(x) \leq \frac{|X|-1}{2}\). On the other hand, \(d_{\overline{X}}^+(x) = d^+(x) – d_X^+(x)\), hence \(d_{\overline{X}}^+(x) \geq \delta – \frac{|X|-1}{2}\). But \(|N^+(X)| \geq d_{\overline{X}}^+(x)\). Therefore, \(|N^+(X)| \geq \delta – \frac{|X|-1}{2}\). ◻
Theorem 2.6. Every oriented graph \(D\) has a pseudo-Seymour set \(S\) such that \(|S|=2\). Moreover, for each \(n \in \{2,3,\ldots,|V(D)|\}\), there is a pseudo-Seymour set \(S_n \subseteq V(D)\) such that \(|S_n|=n\).
Proof. Let \(x\) be a minimum out-degree vertex. If \(\delta = 0\), then \(\{x\}\) is a pseudo-Seymour set. Furthermore, for any \(S \subseteq V(D)\) such that \(\{x\} \subseteq S\), we have \(S\) is a trivial pseudo-Seymour set since \(N^\oplus(S)=\emptyset\). So we can assume that \(\delta \geq 1\). Set \(X = N^+(x)\). Put \(a_1\in X\) such that \(d^+_X(a_1) = \delta_{D[X]}\). Set \(A_1=N^+_X(a_1)\), it is clear that \(|A_1| < \frac{\delta}{2}\). Take \(S=\{x,a_1\}\). Hence \(N^\oplus(S)=A_1\), and so \(|N^\oplus(S)| < \frac{\delta}{2}\). On the other hand, by Lemma 2.5, we have \(|N^+(A_1)| \geq \delta – \frac{|A_1|-1}{2}\), and a trivial verification shows that \(|N^+(A_1)| \geq {\frac{3}{4}}\delta + \frac{1}{2}\). Thus \(|N^{\oplus \oplus}(S)|=|N^+(N^\oplus(S))|=|N^+(A_1)| \geq \frac{3}{4} \delta + \frac{1}{2} > \frac{\delta}{2} > |A_1| = |N^\oplus(S)|\), and therefore \(S\) is a pseudo-Seymour set with \(|S|=2\).
We will now find a pseudo-Seymour set of size \(n\) for any \(n \in \{3,\ldots,|V(D)|\}\). Let \(a_2 \in A_1\) such that \(d^+_{A_1}(a_2)=\delta_{D[A_1]}\). Note that \(\delta_{D[A_1]} < \frac{|A_1|}{2} < \frac{\delta}{4}\). Set \(A_2=N^+_{A_1}(a_2)\). So \(|A_2| = \delta_{D[A_1]} < \frac{\delta}{4}\). Take \(S_3=\{x,a_1,a_2\}\). We thus get \(N^\oplus(S_3)=A_2\), and hence \(|N^\oplus(S_3)| < \frac{\delta}{4}\). By applying Lemma 2.5 to \(A_2\), we obtain \(|N^+(A_2)| \geq \delta – \frac{(|A_2|-1)}{2} \geq \frac{7}{8} \delta + \frac{1}{2}\). It follows that \(|N^{\oplus \oplus}(S_3)|=|N^+(N^\oplus(S_3))|=|N^+(A_2)| \geq \frac{7}{8} \delta + \frac{1}{2} > \frac{\delta}{4} > |A_2| = |N^\oplus(S_3)|\), hence \(S_3\) is a Seymour set with \(|S_3|=3\). In the same manner we can find a pseudo-Seymour set \(S_i=\{x,a_1,\ldots,a_{i-1}\}\). We can continue this process in \(X\) until we obtain \(a_t\) such that \(d_{A_{t-1}}^+(a_t)=0\). Thus \(|N^\oplus(S_{t+1})|=0\), and \(S_{t+1}\) is a trivial pseudo-Seymour set. Since any subset of \(V(D)\) containing \(S_{t+1}\) is a trivial pseudo-Seymour set, we have that there is a pseudo-Seymour set of size \(n\) in \(V(D)\) for each \(n \in \{2,3,\ldots,|V(D)|\}\). ◻
Definition 2.7. Let \(D\) be an oriented graph and let \(X \subset V(D)\). We say that \(X\) has a large out-neighborhood if it satisfies \[|N^+(X)| \geq |X|.\]
Under this definition, \(S\) is a Seymour set if \(N^{\oplus}(S)\) has a large out-neighborhood. Also, \(v\) is a Seymour vertex if \(N^+(v)\) has a large out-neighborhood.
Definition 2.8. We say that \(v\) is a \(\rho\)-Seymour vertex if there exists \(X \subseteq N^+(v)\) such that \(|X|=\lfloor\rho|N^+(v)|\rfloor\) and \(X\) has a large out-neighborhood.
Note that SSNC implies \(\rho=1\). As for the approach giving by Chen, Shen, and Yuster [5], one can make progress on Seymour’s conjecture by maximizing the value of \(\rho\).
Theorem 2.9. Every oriented graph has a \(\rho\)-Seymour vertex such that \(\rho=\frac{2}{3}(1+\frac{1}{2\delta})\).
Proof. Let \(v\) be a minimum out-degree vertex. Let \(X \subseteq N^+(v)\) such that \(|X|=\lfloor\rho|N^+(v)|\rfloor\). So \(|X|=\lfloor \rho \delta \rfloor = \lfloor \frac{2}{3}(\delta+\frac{1}{2}) \rfloor\), it follows that \(|X|\leq \frac{2}{3}(\delta+\frac{1}{2})\). Applying Lemma 2.5 yields \(|N^+(X)| \geq \delta – \frac{(|X|-1)}{2} \geq |X|\), as is easy to check. Thus \(X\) has a large out-neighborhood, and therefore \(v\) is a \(\rho\)-Seymour vertex. ◻
Inspired by the inequality defining a “large out-neighborhood” (denoted hereafter by LON) in the context of the Seymour Second Neighborhood Conjecture (SSNC), we propose several compromise problems that aim to generalize or modify SSNC. Recall that LON refers to the condition: \[|N^+(X)| \geq |X| \quad \text{for some } X \subseteq V(D).\]
The SSNC is equivalent to finding a vertex \(v \in V(D)\) such that \(N^+(v)\) satisfies LON, i.e., \[|N^+(N^+(v))| \geq |N^+(v)|.\]
A natural extension of SSNC is to investigate whether LON holds at higher-order neighborhoods. For \(k \geq 2\), define the \(k\)-th order out-neighborhood recursively as: \[N^{k+}(v) := N^+(N^{(k-1)+}(v)).\]
A natural question is whether there exists a vertex \(v \in V(D)\) satisfying: \[|N^{k+}(v)| \geq |N^{(k-1)+}(v)|.\]
This problem was first proposed in an unpublished manuscript by Burckel (mentioned in Sullivan’s survey [29]) with the additional restriction that the digraph contains no directed cycles of length at most \(k\).
We propose a stronger generalization:
Problem 3.1 (Higher-order depth neighborhood balance). Let \(D\) be a digraph with no directed cycle of length at most \(q\). Can we find a vertex \(v \in V(D)\) such that for all \(p \geq 1\) and \(q \geq p\), the following holds: \[|N^{q+}(v)| \geq |N^{p+}(v)|.\]
Instead of considering the out-neighborhood of a vertex, one may focus on its in-neighborhood. The analogous question is whether there exists a vertex \(v \in V(D)\) whose in-neighborhood satisfies LON, i.e., \[|N^+(N^-(v))| \geq |N^-(v)|.\]
This problem can similarly be extended to higher-order in-neighborhoods defined as: \[N^{k-}(v) := N^-(N^{(k-1)-}(v)), \quad k \geq 2.\]
Problem 3.2 (In-Neighborhood LON).Does there exist a vertex \(v \in V(D)\) in every digraph \(D\) such that: \[|N^+(N^{k-}(v))| \geq |N^{k-}(v)|.\]
Another promising approach is to study LON by interchanging the roles of in- and out-neighborhoods on one side of the inequality. This yields several interesting problems:
Problem 3.3(Sullivan’s Conjecture [29]). Prove or disprove Sullivan’s Conjecture, which asserts that in every digraph \(D\), there exists a vertex \(v\) such that: \[|N^+(N^+(v))| \geq |N^-(v)|.\]
Problem 3.4 (Mixed neighborhood LON).Can we find a vertex \(v \in V(D)\) in every digraph \(D\) such that: \[|N^+(N^-(v))| \geq |N^+(v)|.\]
A natural research direction is to study the family of sets \(S \subseteq V(D)\) that satisfy LON: \[|N^+(S)| \geq |S|.\]
One may ask whether this family of sets exhibits special structural properties.
Problem 3.5 (Structure of sets satisfying LON).Characterize the set of sets \(S \subseteq V(D)\) for which: \[|N^+(S)| \geq |S|.\]