A Remark on the Second Neighborhood Problem

Salman Ghazal^a

^aDepartment of Mathematics Faculty of Sciences I, Lebanese University Beirut - Lebanon.

Institute Camille Jordan Departement de Math ´ ematiques, Universit ´ e Claude Bernard Lyon 1 ´ Lyon - France.

salmanghazal@hotmail.com

Seymour's second neighborhood conjecture states that every simple digraph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). We define "good" digraphs and prove a statement that implies that every feed vertex of a tournament has the SNP. In the case of digraphs missing a matching, we exhibit a feed vertex with the SNP by refining a proof due to Fidler and Yuster and using good digraphs. Moreover, in some cases we exhibit two vertices with SNP.

Keywords: weighted oriented graph, out-neighborhood, second out-neighborhood, matching

Mathematics Subject Classification : 05C20

DOI: 10.5614/ejgta.2015.3.2.6

1. Introduction

In this paper, a digraph D is a pair of two sets (V, D), where E ⊆ V ×V . V and E are the vertex set and edge set of D and denoted by V (D) and E(D) respectively. An oriented graph is a digraph that contains neither loops nor digons. If K ⊆ V (D) then the induced restriction of D to K is

Received: 15 October 2014, Revised: 04 July 2015, Accepted: 25 August 2015.

denoted by D[K]. As usual, \(N_D^+(v)\) (resp. \(N_D^-(v)\)) denotes the (first) out-neighborhood (resp. in-neighborhood) of a vertex \(v \in V\). \(N_D^{++}(v)\) (resp. \(N_D^{--}(v)\)) denotes the second out-neighborhood (in-neighborhood) of v, which is the set of vertices that are at distance 2 from v (resp. to v). We also denote \(d_D^+(v) = |N_D^+(v)|\), \(d_D^+(v) = |N_D^{++}(v)|\), \(d_D^-(v) = |N_D^-(v)|\) and \(d_D^{--}(v) = |N_D^{--}(v)|\). We omit the subscript if the digraph is clear from the context. For short, we write \(x \to y\) if the arc \((x,y) \in E\). A vertex \(v \in V(D)\) is called whole if \(d(v) := d^+(v) + d^-(v) = |V(D)| - 1\), otherwise v is non whole. A sink v is a vertex with \(d^+(v) = 0\). For \(x,y \in V(D)\), we say xy is a missing edge of D if neither (x,y) nor (y,x) are in E(D). The missing graph G of D is the graph whose edges are the missing edges of D and whose vertices are the non whole vertices of D. In this case, we say that D is missing G. So, a tournament does not have missing edges.

A vertex v of D is said to have the second neighborhood property (SNP) if \(d_D^+(v) \leq d_D^{++}(v)\). In 1990, Seymour conjectured the following:

Conjecture 1. (Seymour's Second Neighborhood Conjecture (SNC))[1] Every oriented graph has a vertex with the SNP.

In 1996, Fisher [2] solved the SNC for tournaments by using a certain probability distribution on the vertices. Another proof of Dean's conjecture was established in 2000 by Havet and Thomassé [3]. Their short proof uses a tool called median orders. Furthermore, they have proved that if a tournament has no sink vertex then there are at least two vertices with the SNP.

Let D=(V,E) be a digraph (vertex) weighted by a positive real valued function \(\omega:V\to\mathcal{R}_+\). The couple \((D,\omega)\) (or simply D) is called a weighted digraph. The weight of an arc e=(x,y) is \(\omega(e):=\omega(x).\omega(y)\). The weight of a set of vertices (resp. edges) is the sum of the weights of its members. We say that a vertex v has the weighted SNP if \(\omega(N^+(v)) \leq \omega(N^{++}(v))\). It is known that the SNC is equivalent to its weighted version: Every weighted oriented graph has a vertex with the weighted SNP.

Let \(L=v_1v_2...v_n\) be an ordering of the vertices of a weighted digraph \((D,\omega)\). An arc \(e=(v_i,v_j)\) is forward with respect to L if i< j. Otherwise e is a backward arc. A weighted median order \(L=v_1v_2...v_n\) of D is an order of the vertices of D that maximizes the weight of the set of forward arcs of D, i.e., the set \(\{(v_i,v_j)\in E(D);i< j\}\). In other words, \(L=v_1v_2...v_n\) is a weighted median order of D if \(\omega(L)=\max\{\omega(L');L' \text{ is an ordering of ther vertices of } D\}\). In fact, the weighted median order L satisfies the feedback property: For all \(1\leq i\leq j\leq n\):

\[\omega(N_{D[i,j]}^+(v_i)) \ge \omega(N_{D[i,j]}^-(v_i))\]

and

\[\omega(N_{D[i,j]}^-(v_j)) \ge \omega(N_{D[i,j]}^+(v_j))\]

where \([i, j] := \{v_i, v_{i+1}, ..., v_j\}.\)

Indeed, suppose to the contrary that \(\omega(N_{D[i,j]}^+(v_i)) < \omega(N_{D[i,j]}^-(v_i))\). Consider the order \(L' = v_1...v_{i-1}v_{i+1}...v_{j}v_{i}v_{j+1}...v_{n}\) obtained from L by inserting \(v_i\) just after \(v_j\). Then we have:

\[\begin{split} \omega(L') &= \omega(L) + \omega(\{(v_k, v_i) \in E(D); i \leq k \leq j\}) - \omega(\{(v_i, v_k) \in E(D); i \leq k \leq j\}) \\ &= \omega(L) + \omega(v_i).\omega(N_{D[i,j]}^-(v_i)) - \omega(v_i).\omega(N_{D[i,j]}^+(v_j)) \\ &= \omega(L) + \omega(v_i).(\omega(N_{D[i,j]}^-(v_i)) - \omega(N_{D[i,j]}^+(v_j))) > \omega(L), \end{split}\]

which contradicts the maximality of \(\omega(L)\).

It is also known that if we reverse the orientation of a backward arc \(e = (v_i, v_j)\) of D with respect to L, then L is again a weighted median order of the new weighted digraph \(D' = D - (v_i, v_j) + (v_j, v_i)\).

When \(\omega = 1\), we obtain the definition of median orders of a digraph ([3, 4]).

Let \(L=v_1v_2...v_n\) be a weighted median order. Among the vertices not in \(N^+(v_n)\) two types are distinguished: A vertex \(v_j\) is good if there is \(i \leq j\) such that \(v_n \to v_i \to v_j\), otherwise \(v_j\) is a bad vertex. The set of good vertices of L is denoted by \(G_L^D\) [3] ( or \(G_L\) if there is no confusion ). Clearly, \(G_L \subseteq N^{++}(v_n)\). The last vertex \(v_n\) is called a feed vertex of \((D, \omega)\).

In 2007, Fidler and Yuster [4] proved that SNC holds for oriented graphs missing a matching. They have used median orders and another tool called the dependency digraph. However, there proof does not guarantee that the vertex found to have the SNP is a feed vertex.

In 2012, Ghazal also used the notion of weighted median order to prove the weighted SNC for digraphs missing a generalized star. As a corollary, the weighted version holds for digraphs missing a star, complete graph or a sun [5]. He also used the dependency digraph to prove SNC for other classes of oriented graphs [6].

We say that a missing edge \(x_1y_1\) loses to a missing edge \(x_2y_2\) if: \(x_1 \to x_2\), \(y_2 \notin N^+(x_1) \cup N^{++}(x_1)\), \(y_1 \to y_2\) and \(x_2 \notin N^+(y_1) \cup N^{++}(y_1)\). The dependency digraph \(\Delta\) of D is defined as follows: Its vertex set consists of all the missing edges and \((ab, cd) \in E(\Delta)\) if ab loses to cd [4, 6]. Note that \(\Delta\) may contain digons.

Definition 1. [5] In a digraph D, a missing edge ab is called a good missing edge if:

• (i) \((\forall v \in V \setminus \{a, b\})[(v \to a) \Rightarrow (b \in N^+(v) \cup N^{++}(v))]\) or
• \((ii) \ (\forall v \in V \setminus \{a, b\})[(v \to b) \Rightarrow (a \in N^+(v) \cup N^{++}(v))].\)

If ab satisfies (i) we say that (a, b) is a convenient orientation of ab.

If ab satisfies (ii) we say that (b, a) is a convenient orientation of ab.

We will need the following observation:

Lemma 1.1. [4] Let D be an oriented graph and let \(\Delta\) denote its dependency digraph. A missing edge ab is good if and only if its in-degree in \(\Delta\) is zero.

In the next section, we will define good median orders and good digraphs and prove a statement which implies that every feed vertex of a weighted tournament has the weighted SNP. In the last section, we refine the proof of Fidler and Yuster and use good median orders to exhibit a feed vertex with the SNP in the case of oriented graphs missing a matching.

2. Good median orders

Let D be a (weighted) digraph and let \(\Delta\) denote its dependency digraph. Let C be a connected component of \(\Delta\). Set \(K(C) = \{u \in V(D); \text{ there is a vertex } v \text{ of } D \text{ such that } uv \text{ is a missing edge and belongs to } C \}\). The interval graph of D, denoted by \(\mathcal{I}_D\) is defined as follows. Its vertex set consists of the connected components of \(\Delta\) and two vertices \(C_1\) and \(C_2\) are adjacent if \(K(C_1) \cap K(C_2) \neq \phi\). So \(\mathcal{I}_D\) is the intersection graph of the family \(\{K(C); C \text{ is a connected component of } \Delta \}\). Let \(\xi\) be a connected component of \(\mathcal{I}_D\). We set \(K(\xi) = \bigcup_{C \in \xi} K(C)\). Clearly, if uv is a missing edge in D then there is a unique connected component \(\xi\) of \(\mathcal{I}_D\) such that u and v belong to \(K(\xi)\). For \(f \in V(D)\), we set \(J(f) = \{f\}\) if f is a whole vertex, otherwise \(J(f) = K(\xi)\), where \(\xi\) is the unique connected component of \(\mathcal{I}_D\) such that \(f \in K(\xi)\). Clearly, if \(x \in J(f)\) then J(f) = J(x) and if \(x \notin J(f)\) then x is adjacent to every vertex in J(f).

Let \(L = x_1 \cdots x_n\) be a (weighted) median order of a digraph D. For i < j, the sets \([i,j] := [x_i, x_j] := \{x_i, x_{i+1}, ..., x_j\}\) and \([i,j] = [i,j] \setminus \{x_i, x_j\}\) are called intervals of L. We recall that \(K \subseteq V(D)\) is an interval of D if for every \(u, v \in K\) we have: \(N^+(u) \setminus K = N^+(v) \setminus K\) and \(N^-(u) \setminus K = N^-(v) \setminus K\). The following shows a relation between the intervals of D and the intervals of L.

Proposition 2.1. Let \(\mathcal{I} = \{I_1, ..., I_r\}\) be a set of pairwise disjoint intervals of D. Then for every weighted median order L of D, there is a weighted median order L' of D such that: L and L' have the same feed vertex and every interval in \(\mathcal{I}\) is an interval of L'.

Proof. Let \(L=x_1x_2...x_n\) be a weighted median order of a weighted digraph \((D,\omega)\) and let \(\mathcal{I}=\{I_1,...,I_r\}\) be a set of pairwise disjoint intervals of D. We will use the feedback property to prove it. Suppose \(a,b\in I_1\) with \(a=x_i, b=x_j, i< j\) and \([x_i,x_j]\cap I_1=\{x_i,x_j\}\). Since \(I_1\) is an interval of D, we have \(N_{[i,j]}^+(x_i)=N_{[i,j]}^+(x_j)\) and \(N_{[i,j]}^-(x_i)=N_{[i,j]}^-(x_j)\). So, \(\omega(N_{[i,j]}^-(x_i))\leq \omega(N_{[i,j]}^-(x_j))=\omega(N_{[i,j]}^-(x_i))\), where the two inequalities are by the feedback property. Whence, all the quantities in the previous statement are equal. In particular, \(\omega(N_{[i,j]}^+(x_i))=\omega(N_{[i,j]}^-(x_i))\). Let \(L_1\) be the enumeration \(x_1...x_{i-1}x_{i+1}...x_{j-1}x_{x_i}x_jx_{j+1}...x_n\). Then \(\omega(L_1)=\omega(L)+\omega(N_{[i,j]}^-(x_i))-\omega(N_{[i,j]}^+(x_i))=\omega(L)\). Thus, \(L_1\) is a weighted median order of D. By successively repeating this argument, we obtain a weighted median order in which \(I_1\) is an interval of L. Again, by successively repeating the argument for each \(I\in\mathcal{I}\), we obtain the desired order.

We say that D is \(good\ digraph\) if the sets \(K(\xi)\)'s are intervals of D. By the previous proposition, every good digraph has a (weighted) median order L such that the \(K(\xi)\)'s form intervals of L. Such an enumeration is called a \(good\ (weighted)\ median\ order\) of the good digraph D.

Theorem 2.1. Let \((D, \omega)\) be a good weighted oriented graph and let L be a good weighted median order of \((D, \omega)\), with feed vertex f. Then for every \(x \in J(f)\), we have \(\omega(N^+(x) \setminus J(f)) \le \omega(G_L \setminus J(f))\). So if x has the weighted SNP in \((D[J(f)], \omega)\), then it has the weighted SNP in D.

Proof. The proof is by induction n, the number of vertices of D. It is trivial for n = 1. Let \(L=x_1...x_n\) be a good weighted median order of \((D,\omega)\). Set \(f=x_n, J(f)=[x_t,x_n], L_1=x_1...x_t\)and \(D_1 = D[x_1, x_t]\). Then \((D_1, \omega)\) is a good weighted oriented graph and \(L_1\) is a good weighted median order of \((D_1, \omega)\) in which \(J(x_t) = \{x_t\}\). Suppose that t < n. Then by the induction hypothesis, \(\omega(N_{D_1}^+(x_t)) \leq \omega(G_{L_1})\). However, J(f) is an interval of D, then for every \(x \in J(f)\), we have \(\omega(N^+(x)\backslash J(f)) = \omega(N^+(x_t)\backslash J(f)) = \omega(N^+_{D_1}(x_t)) \leq \omega(G_{L_1}) = \omega(G_L\backslash J(f))\). Now suppose that t=n. If L does not have any bad vertex then \(N^-(x_n)=G_L\). Whence, \(\omega(N^+(x_n))\leq\)\(\omega(N^-(x_n)) = \omega(G_L)\) where the inequality is by the feedback property. Now suppose that L has a bad vertex and let i be the smallest such that \(x_i\) is bad. Since \(J(x_i)\) is an interval of D and L, then every vertex in \(J(x_i)\) is bad and thus \(J(x_i) = [x_i, x_p]\) for some p < n. For \(j < i, x_j\) is either an out-neighbor of \(x_n\) or a good vertex, by definition of i. Moreover, if \(x_i \in N^+(x_n)\) then \(x_i \in N^+(x_i)\). So \(N^+(x_n) \cap [1,i] \subseteq N^+(x_i) \cap [1,i]\). Equivalently, \(N^-(x_i) \cap [1,i] \subseteq G_L \cap [1,i]\). Therefore, \(\omega(N^+(x_n)\cap[1,i])\leq \omega(N^+(x_i)\cap[1,i])\leq \omega(N^-(x_i)\cap[1,i])\leq \omega(G_L\cap[1,i])\), where the second inequality is by the feedback property. Now \(L' = x_{p+1}...x_n\) is good also. By induction, \(\omega(N^+(x_n)\cap [p+1,n])\leq \omega(G_{L'})\). Note that \(G_{L'}\subseteq G_L\cap [p+1,n]\). Whence \(\omega(N^+(x_n))=\)\(\omega(N^{+}(x_{n})\cap[1,i]) + \omega(N^{+}(x_{n})\cap[p+1,n]) \leq \omega(G_{L}\cap[1,i]) + \omega(G_{L}\cap[p+1,n]) = \omega(G_{L}).\)The second part of the statement is obvious.

Since every (weighted) tournament is a good (weighted) oriented graph, we automatically obtain the second neighborhood conjecture for weighted and non-weighted tournaments respectively.

Corollary 2.1. ([4]) Let L be a weighted median order of a weighted tournament \((T, \omega)\) with feed vertex f. Then \(\omega(N^+(f)) \leq \omega(G_L)\).

Corollary 2.2. ([3]) Let L be a median order of a tournament with feed vertex f. Then \(|N^+(f)| \le |G_L|\).

Let L be a good weighted median order of a good oriented graph D and let f denote its feed vertex. By theorem 2.1, for every \(x \in J(f)\), \(\omega(N^+(x)\backslash J(f)) \leq \omega(G_L\backslash J(f))\). Let \(b_1, \cdots, b_r\) denote the bad vertices of L not in J(f) and \(v_1, \cdots, v_s\) denote the non bad vertices of L not in J(f), both enumerated in increasing order with respect to their index in L. If \(\omega(N^+(f)\backslash J(f)) < \omega(G_L\backslash J(f))\), we set Sed(L) = L. If \(\omega(N^+(f)\backslash J(f)) = \omega(G_L\backslash J(f))\), we set \(Sed(L) = b_1 \cdots b_r J(f) v_1 \cdots v_s\). This new order is called the sedimentation of L.

Lemma 2.1. Let L be a good weighted median order of a good weighted oriented graph \((D, \omega)\). Then Sed(L) is a good weighted median order of \((D, \omega)\).

Proof. Let \(L=x_1...x_n\) be a good weighted local median order of \((D,\omega)\). If Sed(L)=L, there is nothing to prove. Otherwise, we may assume that \(\omega(N^+(x_n)\backslash J(x_n))=\omega(G_L\backslash J(x_n))\). The proof is by induction on r the number of bad vertices not in \(J(x_n)\). Set \(J(x_n)=[x_t,x_n]\). If r=0 then we have \(N^-(x_n)\backslash J(x_n)=G_L\backslash J(x_n)\). Whence, \(\omega(N^+(x_n)\backslash J(x_n))=\omega(G_L\backslash J(x_n))=0\)

Define now inductively Sed⁰ (L) = L and Sed^q+1(L) = Sed(Sed^q (L)). If the process reaches a rank q such that Sed^q (L) = y1...yⁿ and ω(N ⁺(yn)\J(yn)) < ω(GSedq(L)\J(yn)), call the order L stable. Otherwise call L periodic. These new order are used by Havet and Thomasse to exhibit ´ a second vertex with the SNP in tournaments that do not have any sink. We will use them for the same purpose but for other classes of oriented graphs.

3. Case of oriented graph missing a matching

In this section, D is an oriented graph missing a matching and ∆ denotes its dependency digraph. We begin by the following lemma:

Lemma 3.1. [4] The maximum out-degree of ∆ is one and the maximum in-degree of ∆ is one. Thus ∆ is composed of vertex disjoint directed paths and directed cycles.

Proof. Assume that a1b¹ loses to a2b² and a1b¹ loses to a 0 2 b 0 2 , with a¹ → a² and a¹ → a 0 2 . The edge a 0 2 b² is not a missing edge of D. If a 0 ² → b² then b¹ → a 0 ² → b2, a contradiction. If b² → a 0 2 then b¹ → b² → a 0 2 , a contradiction. Thus, the maximum out-degree of ∆ is one. Similarly, the maximum in-degree is one.

In the following, C = a1b1, ..., akb^k denotes a directed cycle of ∆, namely aⁱ → ai+1, bi+1 ∈/ N ++(ai) ∪ N ⁺(ai), bⁱ → bi+1 and ai+1 ∈/ N ++(bi) ∪ N ⁺(bi), for all i < k. In [4], it is proved that D[K(C)] has a vertex with the SNP. Here we prove that every vertex of K(C) has the SNP in D[K(C)].

Lemma 3.2. ([4]) If k is odd then a^k → a1, b¹ ∈/ N ++(ak)∪N ⁺(ak), b^k → b¹ and a¹ ∈/ N ++(bk)∪ N ⁺(bk). If k is even then a^k → b1, a¹ ∈/ N ++(ak)∪N ⁺(ak), b^k → a¹ and b¹ ∈/ N ++(bk)∪N ⁺(bk).

Lemma 3.3. [4] K(C) is an interval of D.

Proof. Let f /∈ K(C). Then f is adjacent to every vertex in K(C). If a¹ → f then b² → f, since otherwise b² ∈ N ++(a1)∪N ⁺(a1) which is a contradiction. So N ⁺(a1)\K(C) ⊆ N ⁺(b2)\K(C). Applying this to every losing relation of C yields N ⁺(a1)\K(C) ⊆ N ⁺(b2)\K(C) ⊆ N ⁺(a3)\K(C) · · · ⊆ N ⁺(bk)\K(C) ⊆ N ⁺(b1)\K(C) ⊆ N ⁺(a2)\K(C)· · · ⊆ N ⁺(ak)\K(C) ⊆ N ⁺(a1)\K(C) if k is even. So these inclusion are equalities. An analogous argument proves the same result for odd cycles.

Lemma 3.4. In D[K(C)] we have:

If k is odd then:

\[N^+(a_1) = N^-(b_1) = \{a_2, b_3, \cdots, a_{k-1}, b_k\}\]

\[N^{-}(a_1) = N^{+}(b_1) = \{b_2, a_3, \cdots, b_{k-1}, a_k\},\\]

If k is even then:

\[N^+(a_1) = N^-(b_1) = \{a_2, b_3, \dots, b_{k-1}, a_k\}\]

\[N^{-}(a_1) = N^{+}(b_1) = \{b_2, a_3, \cdots, a_{k-1}, b_k\}.\]

Proof. Suppose that k is odd. Set K:=K(C). Then \(b_k\in N_{D[K]}^+(a_1)\) by lemma 3.2. Since \(a_{k-1}b_{k-1}\) loses to \(a_k,b_k\) and \((a_1,b_k)\in E(D)\) then \((a_1,a_{k-1})\in E(D)\) and so \(a_{k-1}\in N_{D[K]}^+(a_1)\), since otherwise \((a_{k-1},a_1)\in E(D)\) and so \(b_k\in N_{D[K]}^{++}(a_{k-1})\), which is a contradiction to the definition of the losing relation \(a_{k-1}b_{k-1}\to a_kb_k\). And so on \(b_{k-2},a_{k-3},...,b_3,a_2\in N_{D[K]}^+(a_1)\). Again, since \(a_1b_1\) loses to \(a_2,b_2\) then \(b_2\in N_{D[K]}^-(a_1)\). Since \(a_2b_2\) loses to \(a_3,b_3\) and \((b_2,a_1)\in E(D)\) then \((a_3,a_1)\in E(D)\) and so \(a_3\in N_{D[K(C)]}^-(a_1)\). And so on, \(b_4,a_5,...,b_{k-1},a_k\in N_{D[K]}^-(a_1)\). We use the same argument for finding \(N_{D[K]}^+(b_1)\) and \(N_{D[K]}^-(b_1)\). Also we use the same argument when k is even.

Lemma 3.5. In D[K(C)] we have: \(N^+(a_i) = N^-(b_i)\), \(N^-(a_i) = N^+(b_i)\), \(N^+(a_i) = N^-(a_i) \cup \{b_i\} \setminus \{b_{i+1}\}\) and \(N^{++}(b_i) = N^-(b_i) \cup \{a_i\} \setminus \{a_{i+1}\}\) for all i = 1, ..., k where \(a_{k+1} := a_1\), \(b_{k+1} := b_1\) if k is odd and \(a_{k+1} := b_1\), \(b_{k+1} := a_1\) if k is even.

Proof. The first part is due to the previous lemma and the symmetry in these cycles. For the second part it is enough to prove it for i=1 and \(a_1\). Suppose first that k is odd. By definition of losing relation between \(a_1b_1\) and \(a_2b_2\) we have \(b_2 \notin N^{++}(a_1) \cup N^+(a_1)\). Moreover \(a_1 \to a_2 \to b_1\), whence \(b_1 \in N^{++}(a_1)\). Note that for i=1,...,k-1, \(a_i \to a_{i+1}\) and \(b_i \to b_{i+1}\). Combining this with the previous lemma we find that \(N^{++}(a_1) = N^-(a_1) \cup \{b_1\} \setminus \{b_2\}\). Similar argument is used when k is even.

So we have:

Lemma 3.6. \[d^{++}(v) = d^+(v) = d^-(v) = k - 1\] for all \(v \in K(C)\).

Let \(P=a_1b_1,a_2b_2,\cdots,a_kb_k\) be a connected component of \(\Delta\), which is also a maximal path in \(\Delta\), namely \(a_i\to a_{i+1},b_i\to b_{i+1}\) for i=1,...,k-1. Since \(a_1b_1\) is a good edge then \((a_1,b_1)\) or \((b_1,a_1)\) is a convenient orientation. If \((a_1,b_1)\) is a convenient orientation, then we orient \((a_i,b_i)\) for i=1,...,k. Otherwise, we orient \(a_ib_i\) as \((b_i,a_i)\). We do this for every such a path of \(\Delta\). Denote the set of these new arcs by F. Set D'=D+F.

Since we have oriented all the missing edges of D that form the connected components of \(\Delta\) that are paths, then they are no longer missing edges of D' and thus, the dependency digraph of D' is composed of only directed cycles. Then by lemma 3.3 we have:

Lemma 3.7. D' is a good digraph.

Now, we are ready to prove the following statement:

Theorem 3.1. Every feed vertex of D' has the SNP in D and D'.

Proof. Let L be a good median order of D' and let f denote its feed vertex. We have \(|N_{D'}^+(f)\setminus J(f)| \le |G_L^{D'}\setminus J(f)|\) by theorem 2.1.

Suppose that f is not incident to any new arc of F. Then \(J(f)=\{f\}\) or J(f)=K(C) ( in D and D') for some cycle C of \(\Delta\), \(N_{D'}^+(f)=N^+(f)\) and f has the SNP in D[J(f)]. Let \(y\in N_{D'}^{++}(f)\backslash J(f)\). There is a vertex x such that \(f\to x\to y\to f\) in D'. Note that the arcs (f,x) and (y,f) are in D. If \((x,y)\in D\) or is a convenient orientation then \(y\in N^{++}(f)\). Otherwise, there is a missing edge rs that loses to xy, namely \(s\to y\) and \(x\notin N^{++}(s)\cup N^+(s)\). But fs is not a missing edge then we must have \((f,s)\in D\). Thus \(y\in N^{++}(f)\). Hence \(N_{D'}^{++}(f)\backslash J(f)\subseteq N^{++}(f)\backslash J(f)\). Thus \(|N^+(f)|=|N_{D'}^+(f)|=|N_{D'}^+(f)\backslash J(f)|+|N_{D'}^+(f)\cap J(f)|\leq |N^{++}(f)\backslash J(f)|+|N_{D'}^{++}(f)|\).

Suppose that F is incident to a new arc of F. Then there is a path \(P = a_1b_1, a_2b_2, \cdots, a_kb_k\) in \(\Delta\), which is also a connected component \(\Delta\), namely \(a_t \to a_{t+1}, b_t \to b_{t+1}\) for t = 1, ..., k-1, such that \(f = a_i\) or \(f = b_i\). We may suppose without loss of generality that \((a_t, b_t) \in D', \forall t \in \{1, ..., k\}\). Suppose first that \(f = a_i\) and i < k. Then f gains only \(b_i\) as a first out-neighbor and \(b_{i+1}\) as a second out-neighbor. Indeed, let \(y \in N_{D'}^{++}(f) \setminus \{b_{i+1}\}\). There is a vertex x such that \(f \to x \to y \to f\)in D'. Suppose that \(b_i \neq x\). Note that the arcs (f,x) and (y,f) are in D. If \((x,y) \in D\) or is a convenient orientation then \(y \in N^{++}(f)\). Otherwise, there is a missing edge rs that loses to xy, namely \(s \to y\) and \(x \notin N^{++}(s) \cup N^{+}(s)\). But fs is not a missing edge then we must have \((f,s) \in D\). Thus \(y \in N^{++}(f)\). Suppose that \(b_i = x\). Since \(b_i \to y\), \(a_{i+1} \notin N^{++}(b_i) \cup N^+(b_i)\)and \(a_{i+1}y\) is not a missing edge, then we must have \((y,a_{i+1}) \in D\). Thus \(f \to a_{i+1} \to y\) in D and \(y \in N^{++}(f)\). Hence \(N_{D'}^{++}(f)\setminus\{b_{i+1}\}\subseteq N^{++}(f)\). Note that \(J(f)=\{f\}\) in D'. Combining this with theorem 2.1, we get \(|N^+(f)| = |N^+_{D'}(f)| - 1 \le |N^{++}_{D'}(f)| - 1 \le |N^{++}(f)|\). Now suppose that \(f = a_k\). We reorient the missing edge \(a_k b_k\) as \((b_k, a_k)\) and let D'' denote the new oriented graph. Then L is a good median order of the good oriented graph D'', \(N_{D''}^+(f) = N^+(f)\), \(J(f) = \{f\}\) in D", and f has the SNP in D". Let \(y \in N_{D''}^{++}(f)\). There is a vertex x such that \(f \to x \to y \to f\) in D". Note that the arcs (f,x) and (y,f) are in D. If \((x,y) \in D\) or is a convenient orientation then \(y \in N^{++}(f)\). Otherwise, there is a missing edge rs that loses to xy, namely \(s \to y\) and \(x \notin N^{++}(s) \cup N^{+}(s)\). But fs is not a missing edge then we must have \((f,s) \in D\). Thus \(y \in N^{++}(f)\) and \(N_{D''}^{++}(f) \subseteq N^{++}(f)\). Thus f has the SNP in D. Finally, suppose that \(f = b_i\). We use the same argument of the case \(f = a_k\) to prove that f has the SNP in D.

We note that our method guarantees that the vertex f found with the SNP is a feed vertex of some digraph containing D. This is not guaranteed by the proof presented in [4]. Recall that F is the set of the new arcs added to D to obtain the good oriented graph D'. So if \(F = \phi\) then D is a good oriented graph.

Theorem 3.2. Let D be an oriented graph missing a matching and suppose that F = φ. If D has no sink vertex then it has at least two vertices with the SNP.

Proof. Consider a good median order L = x1...xⁿ of D. If J(xn) = K(C) for some directed cycle C of ∆ then by theorem 2.1 and lemma 3.6 the result holds. Otherwise, xⁿ is a whole vertex (i.e. J(xn) = {xn}). By theorem 2.1, xⁿ has the SNP in D. So we need to find another vertex with SNP. Consider the good median order L ⁰ = x1...xn−1. Suppose first that L 0 is stable. There is q for which Sed^q (L 0 ) = y1...yn−¹ and | N ⁺(yn−1)\J(yn−1) |<| GSedq(L0)\J(yn−1) |. Note that y1...yn−1xⁿ is also a good median order of D. By theorem 2.1 and lemma 3.6, y := yn−¹ has the SNP in D[y1, yn−1]. So | N ⁺(y) |=| N + D[y1,yn−1] (y) | +1 ≤| GSedq(L0) |≤| N ++(y) |. Now suppose that L 0 is periodic. Since D has no sink then xⁿ has an out-neighbor x^j . Choose j to be the greatest (so that it is the last vertex of its corresponding interval). Note that for every q, xⁿ is an out-neighbor of the feed vertex of Sed^q (L 0 ). So x^j is not the feed vertex of any Sed^q (L 0 ). Since L 0 is periodic, x^j must be a bad vertex of Sed^q (L 0 ) for some integer q, otherwise the index of x^j would always increase during the sedimentation process. Let q be such an integer. Set Sed^q (L 0 ) = y1...yn−1. Lemma 3.6 and theorem 2.1 guarantee that the vertex y := yn−¹ with the SNP in D[y1, yn−1]. Note that y → xⁿ → x^j and GSedq(L0) ∪ {xj} ⊆ N ++(y). So | N ⁺(y) |=| N + D[y1,yn−1] (y) | +1 =| GSedq(L0) | +1 =| GSedq(L0) ∪ {xj} |≤| N ++(y) |.

References

• [1] N. Dean and B. J. Latka, Squaring the tournament: an open problem, Congress Numerantium 109 (1995), 73-80.
• [2] D. Fisher, Squaring a tournament: a proof of Dean's conjecture, J. Graph Theory 23 (1996), 43–48.
• [3] F. Havet and S. Thomasse, Median Orders of Tournaments: A Tool for the Second Neighbor- ´ hood Problem and Sumner's Conjecture, J. Graph Theory 35 (2000), 244–256.
• [4] D. Fidler and R. Yuster, Remarks on the second neighborhood problem, J. Graph Theory 55 (2007), 208–220.
• [5] S. Ghazal, Seymour's second neighborhood conjecture in tournaments missing a generalized star, J. Graph Theory 71 (2012), 89–94.
• [6] S. Ghazal, A contribution to the second neighborhood problem, Graphs and Combinatorics 29 (2013), 1365–1375.