# Seymour’s Second Neighborhood Conjecture form-Free Oriented Graphs

Authors: Huawen Ma
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

LetD=V,E be an oriented graph with minimum out-degree δ+. For x∈VD, let dD+x and dD++x be the out-degree and second out-degree of x in D, respectively. For a directed graph D, we say that a vertex x∈VD is a Seymour vertex if dD++x≥dD+x. Seymour in 1990 conjectured that each oriented graph has a Seymour vertex. A directed graph D is called m-free if there are no directed cycles with length at most m in D. A directed graph D=V,E is called k-transitive if, for any directed xy-path of length k, there exists x,y∈E. In this paper, we show that (1) each δ+−2-free oriented graph has a Seymour vertex and (2) each vertex with minimum out-degree in m-free and 2m+2-transitive oriented graph is a Seymour vertex. The latter result improves a theorem of Daamouch (2021).


---

## Body

## 1. Introduction

LetD be a directed graph (digraph) with vertex set VD and edge set ED. For any x,y∈VD, we write x⟶y meaning that x,y∈ED and x↛y meaning that x,y∉ED. For a vertex v∈VD, let ND+v=u∈VD|⟶v⟶u and ND++v=w∈VD/ND+v⟶∃x∈ND+v,x⟶w be the out-neighborhood and second out-neighborhood of v, respectively. Let dD+v=⟶ND+v← and dD++v=⟶ND++v← be out-degree and second out-degree of v, respectively. Let δ+D be the minimum out-degree of D. For any A|⊆VD, let DA be the subdigraph of D induced by A. Let NA+v=ND+v∩A and dA+v=⟶NA+v←. Denote by x0,x1,…,xk and x1,x2,…,xk,x1 a directed x0xk-path of length k and a directed k-cycle, respectively. We may omit the subscript if it is clear from the context. For a vertex v∈VD, if dD++v≥dD+v, then we say v is a Seymour vertex. Seymour in 1990 proposed the following conjecture.Conjecture 1 (Seymour’s second neighborhood conjecture).
Each oriented graph has a Seymour vertex.
This conjecture has not been well solved since it was proposed. This problem is widely used in the field of computer network, especially, in fuzzy information and complex network. On the application of this problem, we refer readers to [1–3]. One direction on this conjecture is to consider some specific classes of digraphs. Fisher [4] verified the SSNC for tournaments using a certain probability distribution on the vertices. Havet and Thomassé [5] gave a short proof of SSNC for tournaments using a tool called median orders. Kaneko and Locke [6] proved SSNC for oriented graphs with minimum out-degree smaller than 7. Fidler and Yuster [7] considered the case of tournaments missing a matching. Ghazal [8–10] showed that SSNC holds for tournaments missing n-generalized stars and other class of oriented graphs. A digraph D=V,E is k-transitive (resp., k-quasi-transitive, resp., k-antitransitive) if for any u,v∈V, the existence of a directed path of length k from u to v implies that u⟶v (resp., u⟶v or v⟶u, resp., u↛v). García-Vásquez and Hernández-Cruz [11] proved that SSNC holds for 4-transitive oriented graphs. Gutin and Li [12] proved SSNC for 2-quasi-transitive oriented graphs. Moussa Daamoch [13–15] proved SSNC for 5-antitransitive oriented graphs, k-transitive oriented graphs k≤9, and 3-quasi-transitive oriented graphs.
The other direction on SSNC is to boundγ such that γdD++x≥dD+x for each oriented graph D. Then, Conjecture 1 is γ=1. Chen, Shen, and Yuster [16] showed that γ≥0.657298… is the unique real root in (0, 1) of 2x3+x2−1=0. A digraph D is m-free if D contains no directed cycles with length at most m. Liang and Xu [17] showed that if D is an m-free oriented graph and m⟶+∞, then γ⟶1.
Recently, Moussa Daamoch [14] proved that if D is an m-free digraph, and m≥δ+−1, then D has a Seymour vertex. Naturally, we may ask the following problem: if D is δ+−2-free, whether there exists a Seymour vertex in D or not. In this paper, we first show that SSNC holds for δ+−2-free oriented graphs.Theorem 1.
LetD be an oriented graph with the minimum out-degree δ+. If D is δ+−2-free, then D has a Seymour vertex.A related problem to SSNC is to find more than one Seymour vertex. As we know, a transitive tournament has exactly one Seymour vertex. This problem was proved for some classes of oriented graphs, for example, tournaments, quasitransitive oriented graphs, bipartite tournaments, andk-transitive oriented graphs (see [5,11,12,14,18–21]). Recently, in [14], Daamouch gave the following two results.Theorem 2 (see [4]).
LetD be an m-free and k-transitive oriented graph. If m≥k/2−1, then D has a Seymour vertex.Theorem 3 (see [4]).
LetD be a k-transitive oriented graph. If k≤6, then every vertex with minimum out-degree in D is a Seymour vertex.Combining with the above two theorems, we may ask the following natural problem: for anm-free and k-transitive oriented graph D, whether each vertex with minimum out-degree in D is a Seymour vertex or not. We definitely answered this problem in this paper.Theorem 4.
LetD be an m-free and 2m+2-transitive oriented graph. Then, every vertex with a minimum out-degree in D is a Seymour vertex.In the remainder of this paper, the proof of Theorem1 is given in Section 2, and the proof of Theorem 4 is postponed in Section 3. In Sections 4 and 5, the advantages, limitations, and innovations of this article are summarized. Finally, we sum up a conclusion and propose some open problems.


## 2. Proof of Theorem 1

We first introduce a Lemma due to M. Daamouch [13] before proving Theorem 1, which plays a key role in the proofs of Theorems 1 and 4.Lemma 1 (see Daamouch [13]).
LetD be an oriented graph with the minimum out-degree δ+ and let d+u=δ+. If there exists v∈N+u such that dN+u+v=0, then u is a Seymour vertex.Proof.
|N++u|≥N+v/N+u=N+v≥δ+=N+u.
LetD be an oriented graphs with minimum out-degree δ+. By the theorem of Kaneko and Locke [6], we may assume that δ+≥7. Let u∈VD such that dD+u=δ+ and A=N+u=v0,v1,…,vδ+−1. If there is vi∈A such that dA+vi=0, then u is a Seymour vertex by Lemma 1. So we may assume that dA+vi≥1 for each vi∈A, which implies that DA contains at least 1 directed cycle. Note that D contains no directed cycles with length at most δ+−2. Then, DA must contain a directed cycle with length δ+−1 or δ+. We split it into the following two cases.Case 1.
DA contains a directed cycle of length δ+.
Without loss of generality, assume thatv0,v1,v2,…,vδ+−1,v0 is a directed cycle of length δ+ in DA. Recall that D is δ+−2-free. Then, (1) for each 0≤i≤δ+−3, NA+vi⊆vi+1,vi+2, NA+vδ+−2⊆vδ+−1,v0, and NA+vδ+−1⊆v0,v1. (2) If NA+v0=v1,v2, then NA+v2=v3. Hence, there exists vi∈A such that dA+vi=1. Without loss of generality, we may suppose that NA+v0=v1. If d+v0≥δ++1, then d++u≥dA¯+v0≥δ+=d+u, u is a Seymour vertex. So we suppose that d+v0=δ+. Then, dA¯+v0=δ+−1. We claim that NA¯+vj⊆NA¯+v0, j=1,2. For otherwise, d++u≥NA¯+vj∪NA¯+v0≥δ+=d+u, u is a Seymour vertex.
If there existsx∈B=N+v0 such that dB+x=0, then v0 is a Seymour vertex by Lemma 1. Now, we may suppose that dB+x≥1 for each x∈B which implies that DB contains a directed cycle C, with length δ+−1 or δ+. Note that dB+v1=NA¯+v1≥δ+−2 which implies that v1∉C. (For otherwise, it yields a directed cycle in D of length smaller than δ+−1.) Thus, DB/v1=DNA¯+v0=C, and the length of C is δ+−1. Note that NA¯+v2⊆NA¯+v0 and dB+v2=NA¯+v2≥δ+−2. Then, dB+v1+dB+v2≥2δ+−4>δ+−1. Hence, there exists x∈B/v1 such that v1⟶x and v2⟶x. That is to say, x↛v1 and x↛v2. Then, dB¯+x≥δ+−1. Thus, d++v0≥dB¯+x+v2≥δ+=d+v0, and v0 is a Seymour vertex.Case 2.
DA contains a directed cycle of length δ+−1 and contains no directed cycle of length δ+.
Without loss of generality, we may assume thatv0,v1,v2,…,vδ+−2,v0 is a directed cycle in DA of length δ+−1. Note that dA+vδ+−1≥1. We may suppose that vδ+−1⟶v0. Then, vδ+−2↛vδ+−1. For otherwise, DA contains a directed cycle of length δ+ which implies that dA+vδ+−2=dA+v0=1. If d+v0≥δ++1, then d++u≥dA¯+v0≥δ+=d+u, and u is a Seymour vertex. Hence, we may suppose that d+v0=δ+. And similarly, d+vδ+−2=δ+. Then, dA¯+vδ+−2=dA¯+v0=δ+−1. We claim that NA¯+vδ+−2=NA¯+v0=M. For otherwise, d++u≥NA¯+vδ+−2∪NA¯+v0≥δ+=d+u, and u is a Seymour vertex.
By Lemma1, we may suppose that for each x∈N+vδ+−2, dN+vδ+−2+x≥1 which implies that DN+vδ+−2 contains a directed cycle C′, with length δ+−1. Clearly, v0∉C′. Recall that NA¯+vδ+−2=NA¯+v0=M. Then, DM=C′. If there exists x∈M such that d+x≥δ++1, then d++v0≥dM¯+x≥δ+=d+v0, v0 is a Seymour vertex. Hence, we may assume that for each x∈M, d+x=δ+. We claim that NA¯+v1⊆M. For otherwise, d++u≥M∪NA¯+v1≥δ+=d+u, u is a Seymour vertex. Thus, there exists y∈M such that v1⟶y. That is to say, y↛v1. Note that dM¯y=δ+−1. Hence, d++vδ+−2≥dM¯+y+v1≥δ+=d+vδ+−2. Thus, vδ+−2 is a Seymour vertex, and we are done.


## 3. Proof of Theorem 4

We now give the proof of Theorem4. We spilt this proof into two cases according to whether m larger than δ+−1 and give the following two lemmas.Lemma 2.
LetD be an m-free and 2m+2-transitive oriented graph. If m≥δ+−1, then every vertex with minimum out-degree in D is a Seymour vertex.Proof.
Ifm=2, then by Theorem 3, we are done. So we may suppose that m≥3. It is sufficient to consider m=δ+−1. Let u be a vertex with minimum out-degree. Suppose to contrary that u is not a Seymour vertex. Set N+u=A=x1,x2,…,xm+1. Clearly, DA is m-free. Then, by Lemma 1, DA is a directed cycle of length m+1 which implies that dA+xi=1 and d+xi=δ+=m+1 for 1≤i≤m+1.
We first claim that for any1≤i<j≤m+1, NA¯+xi=NA¯+xj. Since otherwise, d++u≥⟶NA¯+xi∪NA¯+xj⟶≥m+1=δ+=d+u. Thus, u is a Seymour vertex, a contradiction.
Clearly, there exists a vertex, sayxm+2∉A, such that xm+1⟶xm+2. (In fact, for any 1≤i≤m+1, xi⟶xm+2.) Also, there exists a vertex, say xm+3∉A∪u=B, such that xm+2⟶xm+3. We can apply this process until 2m+1, and thus, there exists x2m+1∈N+x2m/B. We claim that N+x2m+1⊆B. For otherwise, there exists a vertex, say y∉B such that x2m+1⟶y. Thus, u,x1,x2,…,x2m+1,y is a directed path of length 2m+2 which implies that u⟶y, a contradiction. Note that N+x2m+1⊆B and δ+=m+1. We next split it into the following two cases according to whether x2m+1 directs to x1.Case 3.
x2m+1⟶x1.
DenoteC=B∪xm+2,xm+3,…,x2m+1. In C, x1 directs to x2 and may directs to xm+2,xm+3,…,x2m. Recall that δ+=m+1 which implies that there exists a vertex, say y1∉C, such that x1⟶y1. Thus, u,x2,x3,,x2m+1,x1,y1 is a directed path of length 2m+2. Recall that D is 2m+2-transitive. Hence, we have u⟶y1, a contradiction.Case 4.
x2m+1↛x1.
Recall thatN+x2m+1⊆B and B=m+2 which implies that x2m+1⟶u. Since D is m-free, x2m does not direct to any vertex except x2m+1 and u in C. Then, there exists a vertex, say y2∉C, such that x2m⟶y2. Thus, x2m+1,u,x1,x2,…,x2m,y2 is a directed path of length 2m+2 which implies that x2m+1⟶y2, a contradiction. □Lemma 3.
LetD be an m-free and 2m+2-transitive oriented graph. If m<δ+−1, then every vertex with minimum out-degree in D is a Seymour vertex.Proof.
As the same proof of Lemma2, we may suppose that m≥3. Let u be a vertex with minimum out-degree. Suppose to contrary that u is not a Seymour vertex. Set N+u=A. Since D is m-free, DA is also m-free. By Lemma 1, we have for each x∈A, dA+x≥1, which implies that DA contains directed cycle of length at least m+1. That is to say, there is a directed path x1,x2,…,xm+1 of length m in DA. Clearly, there exists xm+2∉A∪u=B such that xm+1⟶xm+2. Note that xm+2↛u and xm+2↛xi for each 3≤i≤m+1 since D is m-free. But d+xm+1≥A=δ+, hence, there exists xm+3∉B such that xm+2⟶xm+3. We can apply this process until 2m; thus, there exists x2m∈N+x2m−1/B. We claim that there exists x2m+1∉B such that x2m⟶x2m+1. For otherwise, N+x2m⊆B. Note that x2m↛xm+1 and B=δ++1, which implies that N+x2m=B/xm+1. Recall that δ+>m+1. That is to say, there is a vertex, say y∈A/x1,x2,…,xm+1 such that x2m⟶y. Clearly, there exists y′∉B such that y⟶y′. Since D is m-free and x2m⟶y, y′∉xm+2,xm+3,…,x2m. Thus, u,x1,x2,…,x2m,y,y′ is a directed path of length 2m+2. Since D is 2m+2-transitive, u⟶y′. This contradicts with y′∉A.
Consider the directed pathu,x1,x2,…,x2m+1 of length 2m+1. Since D is 2m+2-transitive, N+x2m+1⊆B. Note that d+x2m+1≥δ+ and B=δ++1. We now split it into the following two cases according to whether x2m+1 directs to u.Case 5.
x2m+1⟶u.
Recall thatN+x2m+1⊆B. Note that x2m+1,u,x1,x2,…,x2m is a directed path of length 2m+1 which implies that N+x2m⊆B. Since D is m-free, x2m↛xm+1. Recall that d+x2m≥δ+ and B=δ++1. Hence, N+x2m=B/xm+1. Recall that δ+>m+1. That is to say, there is a vertex, say z∈A/x1,x2,…,xm+1 such that x2m⟶z. Clearly, there exists z′∉B∪xm+2,…,x2m−1 such that z⟶z′. Thus, u,x1,x2,…,x2m,z,z′ is a directed path of length 2m+2. Since D is 2m+2-transitive, u⟶z′. This contradicts with z′∉A.Case 6.
x2m+1↛u.
Recall thatN+x2m+1⊆B and x2m+1↛u. Then, we have N+x2m+1=A, and there is a vertex, say w∈A/x1,x2,…,xm+1, such that x2m+1⟶w. Clearly, w↛xi for m+3≤i≤2m since D is m-free. Note that u,x2,x3,…,x2m+1,w is a directed path of length 2m+1 which implies that N+w=A∪xm+2/w. Thus, we have x1↛w which implies that there exists a vertex, say x1′∉B∪xm+2, such that x1⟶x1′. Since D is m-free, x1↛xi for m+3≤i≤2m. Thus, u,x2,x3,…,x2m+1,x1,x1′ is a directed path of length 2m+2 which implies that u⟶x1′. This contradicts with x1′∉A.


## 4. Comparison and Analysis

Seymour’s second neighborhood conjecture has always been a classical problem. Much research was done in this field, but it still remains open. It was proven only for some very specific classes of directed graphs. It can be seen that this is not an easy problem. Daamoch [14] showed that if D is an m-free digraph, and m≥δ+−1, then D has a Seymour vertex. We in this paper improve this result in oriented graphs and show that if D is an δ+−2-free oriented graph, then D has a Seymour vertex. In addition, the condition of transitivity is widely used as a limiting condition in this problem. Daamoch [14] showed that if D is an m-free and 2m+2-transitive oriented graph, then D has a Seymour vertex. We in this paper also improve this result and show that each vertex with minimum out-degree in such D is a Seymour vertex. And we believe that the transitivity conditions can be reduced. In this paper, we combine the condition of transitivity with the condition of cycles-free well, and some interesting results are given.


## 5. Advantages and Limitations

Now, we analyze some advantages and limitations of this paper. Firstly, we have indeed improved some important results of predecessors although the improvement is not too heavy. Second, in the proofs of theorems, we used some innovative methods, which provide some new ideas for future proofs. However, our method is only applicable to digraphs without short cycles. For digraphs with short cycles, new ideas are still needed. Third, this thought can be applied to other problems of graph theory, such as graph partitioning and coloring. Given an oriented graphD, we can partition VD into V1 and V2 by placing each vertex v∈VD into V1 if there exists a directed path of length k between v and a fixed vertex u, and placing into V2 otherwise. Also, the thought can be applied to solving the indexes of graphs [22–28].


## 6. Conclusion and Future Research

Based on Theorems1 and 4, we propose the following natural problems.Problem 1.
What is the largest positive integerk, such that each δ+−k-free-oriented graph has a Seymour vertex?
Obviously, Theorem1 shows that k≥2. When k=3, we believe that the conclusion is also true, but more details need to be considered in the proof. For Theorem 4, we propose the following problem.Problem 2.
LetD be an m≥3-free and 2m−2-transitive oriented graph. Then, whether each vertex with minimum out-degree in D is a Seymour vertex or not?
Clearly, here, we reinforce the condition of transitivity. Then, a lot of structures will be added to the oriented graphs, and we also need to consider more structures of oriented graphs.



---

*Source: 1463016-2022-08-11.xml*