1 Introduction↩︎

We introduce Seymour-tight orientations, motivated by the equality case in Seymour’s second neighbourhood conjecture and as a natural symmetry condition for oriented graphs. We proceed with some definitions. Let \(G\) be a directed graph. The out-neighbourhood of a vertex \(v \in V(G)\) is the set \(N^{}_{1}(G,v) := \{ w \in V(G) \mid (v,w) \in E(G)\}\). It consists precisely of the vertices \(w\) for which there is an arc from \(v\) to \(w\). The second out-neighbourhood of \(v\) is \[N^{}_{2}(G,v) := \left\{ w\in V(G) - ( N^{}_{1}(G,v) \cup \{v\}) \, \middle\vert \, \exists u \in N^{}_{1}(G,v) \text{ s.t. } (u,w) \in E(G)\right\}.\] Thus, it consists of all vertices that can be reached in two steps, but not less, from \(v\). An orientation is a digraph that contains no cycles of length 2. Equivalently, it can be seen as an assignment of a direction to each edge of an undirected graph. The following is known as Seymour’s second neighbourhood conjecture.

This open conjecture, which is related to the Caccetta-Häggkvist conjecture [1], has received considerable attention [2]–[6]. It is known to hold for several special classes of digraphs. In particular, it was solved for tournaments by Fischer [7] (see also an alternative proof by Havet and Thomassé [8]), confirming a conjecture of Dean [9].

Chen, Shen and Yuster [10] proved that every orientation \(G\) has a vertex \(v\) satisfying \(| N^{}_{2}(G,v)| \geq \gamma | N^{}_{1}(G,v)|\) where \(\gamma = 0.657298\ldots\), the unique real root of \(2x^3+x^2-1=0\). This constant \(\gamma\) was recently improved by Huang and Peng to 0.715538 [11]. Espuny Díaz, Girão, Granet and Kronenberg [12] have shown for all \(p<\frac{1}{2}\) that the conjecture holds for all orientations of \(G(n,p)\) a.a.s. (with probability tending to 1 as \(n \rightarrow \infty\)). Moreover, they proved that if the conjecture is false then for all \(p \in (\frac{1}{2},1)\), there exists a.a.s. an orientation of \(G(n,p)\) which is a counterexample. A counterexample \(G\) to Seymour’s second neighbourhood conjecture satisfies \(| N^{}_{1}(G,v)| > | N^{}_{2}(G,v)|\) for all \(v \in V(G)\); properties of (minimal) counterexamples have been studied. For example, the minimum out-degree of a counterexample is at least \(7\) [13] and satisfies \(\delta^{+}(G) \geq \sqrt{|V(G)|}\) [12]. Further, if there exists a counterexample with minimum out-degree \(\delta\), then there exists a counterexample on at most \(\binom{\delta+1}{2}\) vertices [14].

Rather than putative counterexamples, what are the properties of graphs that are close to counterexamples? We are interested in orientations that satisfy \(| N^{}_{1}(G,v)| \geq | N^{}_{2}(G,v)|\) for all \(v \in V(G)\). Note that by adding a universal sink \(s\), we get an orientation where \(| N^{}_{1}(G,s)| = | N^{}_{2}(G,s)|=0\) and \(| N^{}_{1}(G,v)| > | N^{}_{2}(G,v)|\) for all \(v \neq s\); loosely speaking, we may think of these as being as close to a counterexample as possible. For convenience, we call orientations satisfying \(| N^{}_{1}(G,v)| \geq | N^{}_{2}(G,v)|\) for all \(v \in V(G)\) Seymour orientations.

Within this class of orientations, we mostly focus on those that are tightest with respect to the condition, which we might consider a type of symmetry. We say that an orientation \(G\) is Seymour-tight if \(| N^{}_{1}(G,v)| = | N^{}_{2}(G,v)|\) for all \(v \in V(G)\). Focusing on symmetric graphs has often been a useful strategy to construct extremal examples and/or counterexamples. Seymour-tight orientations give us a better understanding of how counterexamples to Seymour’s second neighbourhood conjecture may arise. We will see that the class of Seymour-tight orientations are closed under taking lexicographic products. Based on this, we observe that the lexicographic product of a counterexample and a Seymour orientation, in either order, is a counterexample [15]. Among other applications, we use this observation to show that there are counterexamples (if one exists) that are close to (regular) tournaments (Corollary [Close32to32reg32tournament]), and to show the following result.

We also present other ways to build up Seymour-tight orientations from other Seymour-tight orientations, see Figure 1. In Section 4, we show that we can replace subgraphs on which all other vertices are uniform. Hence, the class of Seymour-tight orientations is closed under taking generalized lexicographic products. In Section 5, we describe how to add a source component to a Seymour-tight orientation to obtain a strongly disconnected Seymour-tight orientation. In Section 6, we apply our methods to construct Sullivan-tight orientations and special putative counterexamples to Sullivan’s conjecture.

Any vertex-transitive Seymour orientation is either a counterexample or a Seymour-tight orientation. It is therefore natural to ask about Seymour(-tight) orientations with more symmetry; it is a classic result of Hamidoune [16] that there are no Cayley counterexamples. We observe in Section 7 that the connection sets of Seymour Cayley orientations correspond to critical pairs of sets in groups, giving a nice connection to structural additive combinatorics [17]. We use a result of Kemperman [18], about critical pairs in abelian groups, to classify all Seymour abelian Cayley orientations.

While the hypothesis is algebraic, the conclusion is purely combinatorial. It is natural to wonder if the same combinatorial classification extends to Seymour orientations that are Cayley digraphs or that are vertex-transitive. In the concluding section of the paper, we discuss this and other open problems. In particular, we pose some problems related to conditions for Seymour-tight orientations such that its converse is also Seymour-tight.

2 Examples and basic properties↩︎

We start by giving a few examples of Seymour-tight orientations. Note that any directed cycle \(\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_n}\vphantom{\mathrm{\small f}}}\mkern 2mu\), \(n \geq 3\), is a Seymour-tight orientation, as every vertex has one vertex in its out-neighbourhood and one vertex in its second out-neighbourhood. In the \(k\)-th power of a directed graph \(D\), denoted by \(D^k\), there is an arc from \(v\) to \(w\) if and only if there is a path of length at most \(k\) from \(v\) to \(w\) in \(D\).

The \(k\)-th power of a directed cycle of length \(n\) is a Cayley digraph of \(\mathbb{Z}_n\) with connection set \(\{1, \ldots,k \}\). Next, we characterize which tournaments are Seymour-tight orientations.

Two vertices \(u,v \in V(D)\) lie in the same strongly connected component of a directed graph \(D\) if there exists a directed walk from \(u\) to \(v\) and a directed walk from \(v\) to \(u\). A directed graph \(D\) is strongly connected if it has only one strongly connected component. Every directed graph can be partitioned into its strongly connected components \(A', \ldots, A_k\). The condensation of \(D\) is the graph where every strongly connected component is contracted into one vertex. There is an arc \(A_i \rightarrow A_j\) in the condensation if and only if there exist \(v \in A_i\) and \(w \in A_j\) such that \(v \rightarrow w\) is an arc in \(D\).

By definition, the condensation of \(D\) is a directed acyclic graph. Let \(\mathcal{A}_k\) be the set of \(A_i\) that can be reached from \(A_k\) in the condensation of \(D\). If \(D\) is a Seymour-tight orientation, then \(\mathcal{A}_k\) is also a Seymour-tight orientation for all \(k\). In particular, all \(A_i\) that are sink vertices in the condensation of \(D\) are Seymour-tight orientations. Hence, every strongly disconnected Seymour-tight orientation can be formed by starting with a strongly connected Seymour-tight orientation and then adding ‘source’ components to it, see Section 5.

In Sections 3 and 4, we show that the class of Seymour-tight orientations is closed under taking (generalized) lexicographic products. If \(D\) is strongly connected, then \(D[G_1, \ldots, G_k]\) is also strongly connected even if (some of) the \(G_i\)’s are not. Hence, we can construct a strongly connected Seymour-tight orientations from strongly disconnected Seymour-tight orientations \(G_1,\ldots, G_k\) each on \(n\) vertices by taking a generalized lexicographic product \(D[G_1,\ldots,G_k]\) where \(D\) is a strongly connected Seymour-tight orientation on \(k\) vertices.

3 Lexicographic products↩︎

Let \(D\) and \(G\) be two directed graphs, then the lexicographic product of \(D\) and \(G\), denoted \(D[G]\) satisfies \(V(D[G])=V(D) \times V(G)\). There is a directed edge from \((v,i)\) to \((w,j)\) if and only if there is a directed edge from \(v\) to \(w\) in \(D\) or \(v=w\) and there is a directed edge from \(i\) to \(j\) in \(G\) [19]. Hence, the lexicographic product of two orientations is again an orientation. Moreover, the underlying graph of \(D[G]\) is the lexicographic product of the underlying graph of \(D\) with the underlying graph of \(G\).

3.1 Putative counterexamples↩︎

With the lexicographic product, we can not only construct new Seymour-tight orientations, but also obtain counterexamples from smaller ones. Using similar arguments as in the proof of Lemma [Seymour32lex], we can show the following.

In particular, we can take \(G\) to be Seymour-tight. By choosing \(G\) appropriately, we can construct counterexamples that satisfy some interesting properties.

Similarly, by taking \(G=\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_n}\vphantom{\mathrm{\small f}}}\mkern 2mu\), we observe that there exists \(k \in \mathbb{N}\) such that there are infinitely many counterexamples of maximum degree at most \(k\) [12]. By repeatedly taking the lexicographic product of counterexamples, we obtain the following result.

So Seymour’s second neighbourhood conjecture is equivalent to the following conjecture:

3.2 Induced subgraphs↩︎

In this subsection, we prove that every oriented graph is an induced subgraph of a Seymour-tight orientation.

Using this we can prove that if Seymour’s second neighbourhood conjecture is false, then any orientation is an induced subgraph of a counterexample.

4 Generalized lexicographic products↩︎

Let \(X \subseteq V(D)\) be a set of vertices in a Seymour-tight orientation \(D\). A vertex \(v \in D-X\) is uniform on X if one of the following holds:

1. all vertices in \(X\) are in-neighbours of \(v\);

2. all vertices in \(X\) are out-neighbours of \(v\); or

3. no vertex in \(X\) is an in- or out-neighbour of \(v\).

So for any \(v \in D-X\), we have that either \(v\) is in the second out-neighbourhood (resp. second in-neighbourhood) of all vertices in \(X\) or in the second out-neighbourhood (resp. second in-neighbourhood) of no vertex in \(X\). In particular, the number of vertices in \(D-X\) in the first and second neighbourhood of some vertex \(x \in X\) does not depend on the particular vertex \(x \in X\). If \(D\) is a Seymour-tight orientation, there exists \(k \in \mathbb{Z}\) such that for all \(x \in X\), \(| N^{}_{1}(D|_X,x)|-| N^{}_{2}(D|_X,x)|=k\).

Let \(D[G]\) be the lexicographic product of two Seymour-tight orientations \(D\) and \(G\). Then for every \(v \in D\), define the set \(X_v = \{(v,i) \mid i \in V(G)\}\).

The generalized lexicographic product is also known as \(H\)-join. By applying Lemma [lem:32replace32lex32prod] to every set \(X_v\) in the lexicographic product \(D[G]\), we obtain the following.

Using this, we can construct infinitely many non-regular strongly connected Seymour-tight orientations, since the \(G_i\) can be chosen arbitrarily. Taking for example \(D=\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\), \(G_1=G_2 = E_3\) and \(G_3 = \mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\), we get a Seymour-tight orientation on 9 vertices where some vertices have out-degree 3 while others have out-degree 4, see Figure [fig:non95reg95example]. Or we might have \(D=\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_4}\vphantom{\mathrm{\small f}}}\mkern 2mu\), \(G_1 =\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_4}\vphantom{\mathrm{\small f}}}\mkern 2mu\), \(G_2= \mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu \cup K_1\), \(G_3=E_4\) and \(G_4\) consists of \(\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\) with an extra vertex that has one outgoing arc pointing towards a vertex on this cycle, see Figure [fig:non95reg2].

Similarly, we can also extend Theorem [Lex32product32counterexample] to also hold for generalized lexicographic products.

Note that we could have used this type of proof also to prove Corollary [vervang32alle32punten]. We can use even more generalized lexicographic-type products to make new Seymour-tight orientations. Following [20], we define the matrix \(S_D\) with entries given by \[S_D(v,w) = \begin{cases} 1, & \text{ if }w \in N_1(v); \\ -1, & \text{ if } w \in N_2(v); \\ 0, & \text{ otherwise.} \end{cases}\] By construction, \(S_D \mathbf{1}=0\) if and only if \(D\) is a Seymour-tight orientation. Moreover, an orientation is a Seymour orientation if and only if \(S_D \mathbf{1} \leq 0\). The matrix \(S_D^{T}\) corresponds to converse, which is the orientation where all arcs are reversed. We will consider specific vectors in the kernel of \(S_D\), which is a subspace of \(\mathbb{R}^n\). Since \(S_D\) is an integral matrix, there exists a basis of the kernel of \(S_D\) with integer entries.

With this result we can even take generalized lexicographic products of some graphs that are not all the same size.

In light of this, every linear combination of vectors \(\chi_i\) where \(i \in \{1, \ldots, \frac{n}{d}\}\) lies in the kernel of \(S_D\). We can use these vectors to construct more examples of Seymour-tight orientations. For example, take \(D=\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_6}\vphantom{\mathrm{\small f}}}\mkern 2mu^2\). Then \(d=\gcd(6,2)=2\). Thus the vector \(\chi_1+3\chi_2=(1,3,1,3,1,3)^T\) lies in the kernel of \(S_D\). Hence, we can take \(G_1=G_3=G_5=K_1\) to be Seymour-tight orientations on one vertex and \(G_2=G_4=E_3\) and \(G_6=\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\) to be Seymour-tight orientations on three vertices. This construction results in the graph in Figure 3.

Lemma [lem:32replacement] can also be applied to other Seymour-tight orientations than lexicographic products. For example, a regular tournament can contain one or multiple small regular tournaments on which all other vertices are uniform. Then we can replace these small tournaments with some other Seymour-tight orientations to obtain a new Seymour-tight orientation that is not necessarily a regular tournament, see Figure 4.

4.1 Seymour-tight orientations with out-degree at most 2↩︎

Throughout the paper, we will see that lexicographic products are a powerful tool; in this section, we see that it is the only tool we need to characterize strongly connected Seymour-tight orientations with out-degree at most 2. Note that a graph \(D\) containing a vertex \(v\) of out-degree zero is strongly connected only if \(D=\{v\}\). Hence, we may assume that every vertex in \(D\) has at least one out-neighbour. We will give a characterization based on whether there exists a vertex of out-degree exactly \(1\) or \(2\).

Directed cycles are strongly connected Seymour-tight orientations in which every vertex has out-degree one. We will now show these are the only strongly connected Seymour-tight orientation that have a vertex of out-degree one.

Next, we characterize all strongly connected Seymour-tight orientations with a vertex of out-degree 2.

If a strongly connected Seymour-tight orientation \(D\) has a vertex of out-degree \(1\) or \(2\), then it follows from Lemmas [lem:out-degree1] and [lem:out-degree2] that \(D\) is out-regular. We note that this property does not extend to higher out-degree; as seen in Figure [fig:non95reg95example], there are Seymour-tight orientations that have a vertex of out-degree 3 that also contain vertices with higher out-degrees.

5 Strongly disconnected Seymour-tight orientations↩︎

As we have seen in Section 2, every strongly disconnected Seymour-tight orientation can be formed by adding source components to a Seymour-tight orientation. In this section, we give two such constructions.

6 Sullivan’s conjecture↩︎

Let \(G\) be a directed graph. Then \(N^{-}_{1}(G,v) = \{u \in V(G) \mid uv \in E(G)\}\) is the in-neighbourhood of the vertex \(v\). In her survey on the Caccetta-Häggkvist conjecture [21], Sullivan proposed the following variation of Seymour’s conjecture.

Note that this conjecture coincides with Seymour’s second neighbourhood conjecture when restricted to Eulerian orientations. Sullivan’s conjecture has received significantly less attention. Nevertheless, it is known to hold for tournaments, for graphs in which the number of transitive triangles is small relative to the number of arcs, and for almost all oriented graphs [22]. Analogous to Seymour-tight orientations, we call an orientation \(G\) a Sullivan-tight orientation if \(| N^{-}_{1}(G,v)|=| N^{+}_{2}(G,v)|\) for all \(v \in V(G)\).

We will start by giving a few examples.

Note that every regular tournament has diameter 2, but not every tournament with diameter 2 is a regular tournament. Hence, there are Sullivan-tight orientations that are not Seymour-tight orientations, see Figure 5. We now prove that Sullivan-tight orientations do not have sinks and all sources should be universal sources. Hence, our constructions for Seymour-tight orientations from Section 5 do not extend for Sullivan-tight orientations.

However, (generalized) lexicographic products preserve not only Seymour-tight orientations, but also Sullivan-tight orientations.

Notice in the proof that the only information about \(G\) we needed was \(|V(G)|\) and by the same argument have the following result.

Let \(D\) be an orientation. Let \(R_D\) be the matrix defined by \(R_D(v,w)=1\) if \(w \in N^{+}_{2}(D,v)\setminus N^{-}_{1}(D,v)\) and \(R_D(v,w)=-1\) if \(w \in N^{-}_{1}(D,v) \setminus N^{+}_{2}(D,v)\) and \(R_D(v,w)=0\) elsewhere. In particular, \(R_D(v,w)=0\) if \(w \in N^{-}_{1}(D,v) \cap N^{+}_{2}(D,v)\). By definition, \(S_D \mathbf{1}=0\) if and only if \(D\) is a Sullivan-tight orientation.

Since \(R_D(v,w)=0\) if \(w \in N^{-}_{1}(D,v) \cap N^{+}_{2}(D,v)\), there are graphs for which there are many zeros in \(R_D\) implying a large kernel. For example, for a directed triangle \(\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\), we have \(R_{\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu}=\boldsymbol{0}\). Hence, any vector in \(\mathbb{Z}_{>0}\) lies in the kernel of \(R_{\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu}\).

6.1 Putative counterexamples to Sullivan’s conjecture↩︎

We can also prove analogous results to those in Subsection 3.1. As the proofs are very similar to the proofs of their respective results for Seymour-tight orientations, for brevity we only give proof sketches.

7 Seymour Cayley orientations↩︎

In this section, we will look at Cayley digraphs that are also Seymour orientations. Recal that any Cayley graph is vertex transitive and therefore any Cayley Seymour orientation is either a counterexample or Seymour-tight. Let \(\Gamma=\Gamma(G,S)\) be a Cayley digraph and a Seymour orientation. The connection set \(S\) satisfies \(S \cap S^{-1} = \emptyset\). Moreover, \(| N^{+}_{1}(G,v)| = |S|\) and \(| N^{+}_{1}(G,v) \cup N^{+}_{2}(G,v)|=|S^2 \cup S|\), thus it must satisfy \(|S \cup S^2| \leq 2|S|\). Let \(S_1=S\cup\{1\}\) where \(1\) is the identity element. Then \(S_1^2= S \cup S^2 \cup \{1\}\) and since, \(S \cap S^{-1} = \emptyset\), the only way to write \(1\) as the product of two elements in \(S_1\) is as \(1=1\cdot 1\). In particular, \[|S_1^2| = |S \cup S^2| + 1 \leq 2|S|+1 = 2|S_1|-1.\] A pair \(A,B \subseteq G\) for which \(|AB| < |A|+|B|\) is called a critical pair. The study of critical pairs is an important topic within structural additive combinatorics [17]. Kemperman proved the following result.

Kemperman’s Lemma implies \(|S_1^2| = 2|S_1|-1\) and thus \(S\) satisfies \(|S^2 \cup S| = 2 |S|\). Therefore, any Seymour Cayley orientation is Seymour-tight. In particular, there is no Cayley counterexample, which was first observed by Hamidoune [16]. From now on, we will write Seymour orientation for brevity (although they are actually Seymour-tight).

To classify all Seymour Cayley orientations, we have to find all sets \(S\) for which the inequality in Lemma [Lem:32Kemperman] is tight for the pair \((S,S)\). Kemperman [18] classified all such pairs of sets in abelian groups. We will use this result to prove that any Seymour Cayley orientation is the (possibly repeated) lexicographic products of empty graphs, the \(k\)-th power of directed cycles, and regular tournaments. We first need to introduce some notation; note we will use additive notation for groups while discussing abelian groups.

Observe that each of the conditions \((a)-(d)\) implies \(|A'+B'|=|A'|+|B'|-1\). We reformulate [18] below, avoiding specialized notation.

Based on this theorem, we can classify all Seymour orientations that are Cayley digraphs of an abelian group.

It is remarkable that this classification is completely combinatorial and does not depend the exact abelian group of the Cayley graphs. Therefore, one can ask of this classification holds for a larger class of Seymour orientations, see the following conjecture:

We can ask if it for all vertex-transitive Seymour orientations.

DeVos [23] extended Kemperman’s result to non-abelian groups, which suggests a possible approach to (dis)prove Conjecture [conjecture32cayley]. Specifically, DeVos characterizes all maximal critical pairs up to similarity. Observe that a pair \((A,B)\) is critical if and only if \((gA,B)\) or \((A^{-1},B^{-1})\) is. These pairs are called similar. Also, note that the pair \((S_1,S_1)\) is not necessarily maximal. Therefore, to determine all connecting sets \(S\) of Seymour orientations, one should look at which pairs of sets in his characterization are similar to a pair that contains a critical pair \((S_1,S_1)\) such that \(S_1 \cap S_1^{-1}=\{1\}\). Applying this characterization to our problem appears to necessitate a highly technical analysis beyond the scope of the present paper.

However, as a proof of concept, we can look at which trios described in Theorem 2.3 in [23] contain two copies of a set \(S_1\) satisfying \(S_1 \cap S_1^{-1} = \{1\}\). Let \(\Phi_1,\ldots,\Phi_m\) be the sequence such that \(\Phi_{i}\) lies in some group \(G_{i}\) and where \(\Phi_i\) is a ‘continuation’ of \(\Phi_{i-1}\). Since \(S_1 \cap S_1^{-1} = \{1\}\), every \(\Phi_{i}\) contains twice a set \(S_1 \cap G_i=X_i\) satisfying \(X_i \cap X_{i}^{-1} = \{1\}\). Moreover, \(X_{i-1}-X_i\) the union of cosets of \(G_i\) in \(G_{i-1}\). Thus, the Cayley graph \(\Gamma(G_{i-1},X_{i-1}-\{1\})\) is the lexicographic product of \(\Gamma(G_{i-1} \slash G_i , (X_{i-1} \backslash X_i)\slash G_i)\) with \(\Gamma(G_i,X_i-\{1\})\).

Note that the two sets \(X_i\) have the same size. Thus, any (impure) beat corresponds to a regular tournament \((|B|=|C|)\) or to a disjoint union of smaller graphs if \(|A|=|B|< G_{i+1}\). Similarly, any (impure) chord corresponds to a \(k\)-th power of a directed cycle as both \(A-X_{i+1}\) and \(B-X_{i+1}\) are geometric sets. Moreover, \(X_i \cap X_i^{-1}=\{1\}\) implies that \(\Phi_i\) cannot be an impure dihedral chord. Lastly, all sporadic cases for \(\Phi_m\) are not possible if we assume that two sets are equal to \(X_m\) satisfying \(X_m \cap X_m^{-1}= \{1\}\).

8 Discussion↩︎

In this paper, we have given some examples and general methods to construct Seymour-tight and Sullivan-tight orientations. We used these methods to construct special putative counterexamples to these conjectures. Additionally, we classified all Seymour-tight Cayley orientations of abelian groups. A natural goal would be to obtain a (partial) classification of general Seymour-tight orientations or to establish further structural properties. Progress towards this might correlate with significant progress on Seymour’s second neighbourhood conjecture itself.

In addition to Conjecture [conjecture32cayley], another class of highly symmetric digraphs where the classification of Seymour-tight graphs may be tractable is the class of distance transitive orientations. Lam [24] observed that directed cycles and Paley tournaments are distance transitive digraphs. Moreover, he proved that the lexicographic product of a distance transitive graph with the empty graphs gives a new distance transitive graph. Note that these graphs are all Seymour-tight orientations. Bannai, Cameron and Kahn [25] proved that there are no other distance transitive digraphs of odd girth. We conjecture the following.

This might be an interesting intermediate step towards classifying all distance transitive digraphs (of even girth).

We have seen that the basic examples of Seymour-tight orientations, namely the \(k\)-th power of a directed cycle and regular tournaments, exhibit symmetry and regularity. However, using generalized lexicographic products, we can also construct many strongly connected Seymour-tight orientations that do not have symmetry or regularity, see Figure 2.

Another question is whether the converse, which is the orientation where all arcs are reversed, of a Seymour-tight orientation is again a Seymour-tight orientation. This is not true for all (strongly connected) Seymour-tight orientations. As an example, take \(G\) to be \(\mkern 2mu\overrightarrow{\mkern-2mu\smash{C_3}\vphantom{\mathrm{\small f}}}\mkern 2mu\) with an extra vertex \(u\) that has one outgoing arc pointing towards a vertex \(v\) on this cycle. Then the converse of \(G\) is not a Seymour-tight orientation. The vertex \(v\) has namely two in-neighbours in \(G\), but only one vertex in its second in-neighbourhood. By taking the lexicographic product of a directed cycle \(D\) with \(G\), we obtain a strongly connected Seymour-tight orientation whose converse is not Seymour-tight.

On the positive side, this converse-invariance holds if we impose additional symmetry conditions, namely, the converse of any vertex-transitive Seymour-tight orientation is Seymour-tight. Indeed, for any vertex-transitive orientation \(O\), there exists \(k\) and \(m\) such that \(| N^{+}_{1}(O,v)|=| N^{-}_{1}(O,v)|=k\) and \(| N^{+}_{2}(O,v)|=| N^{-}_{2}(O,v)|=m\). If \(O\) is also Seymour-tight, then \(k =| N^{+}_{1}(O,v)|=| N^{+}_{2}(O,v)|=m\) and thus also \(| N^{-}_{1}(O,v)|= | N^{-}_{2}(O,v)|\). This naturally leads to the following question: is the converse of a Seymour-tight orientation also Seymour-tight, under the weaker assumption that every vertex has in- and out-degree \(k\)? We conjecture that this is the case.

Note that the conjecture holds for \(k=1\) and \(k=2\), by Lemmas [lem:out-degree1] and [lem:out-degree2]. One could even pose a stronger question: does the converse property still hold if we relax the uniformity of the constraint from the parameter \(k\)?

Note that this statement is true for Eulerian orientations of regular tournaments, powers of directed cycles, empty graphs and their (repeated) generalized lexicographic products. Moreover, the following construction preserves Seymour-tightness under the converse operation: take a regular tournament which contains some small regular tournament on which all other vertices are uniform, and then replace that small regular tournament with some other Seymour-tight orientation \(S\) satisfying \(| N^{-}_{1}(S,v)|=| N^{+}_{1}(S,v)|=| N^{+}_{2}(S,v)|=| N^{-}_{2}(S,v)|\) for all \(v\).

Seymour’s second neighbourhood conjecture in the context of Eulerian digraphs has been studied by Cary [26], who showed that if an Eulerian digraph \(G\) admits a simple cycle partition, then Seymour’s second neighbourhood conjecture holds for \(G\).

Acknowledgements↩︎

RK was partially supported by the Dutch Research Council (NWO) grant OCENW.M20.009 and the Gravitation Programme NETWORKS (024.002.003) of the Dutch Ministry of Education, Culture and Science (OCW).

Open access statement↩︎

For the purpose of open access, a CC BY public copyright license is applied to any Author Accepted Manuscript (AAM) arising from this submission.

References↩︎