## Special cases

Although SSNC has not been proven yet foralloriented graphs, there exist several proofs of special families of oriented graphs. Below, you will find a couple of articles with such proofs. To read a summary of and comments on the article, please click on the links below to fold out the menu. If you want to read the article itself, you can click on the PDF logo next to the author's name.

A Combinatorial Proof of Seymour's Conjecture for Regular Oriented Graphs with Regular Outsets, Lester MackeyO'and_{a}O''_{a}Via proof by contradiction, Mackey proves SSNC for regular oriented graphs

G= (V,E) with regular setsO'and_{a}O''for some_{a}a∈V. To this end, he defines the outset and the second degree outset of a vertex. Theoutsetof a vertexa, denoted, is the set of all vertices to which an out-going edge extends fromO'_{a}a. Thesecond degree outset,, may be defined as the union of the outsets of allO''_{a}xinO'minus_{a}O'. In his proof, Mackey applies an inventive combinatorial method involving estimations of the outset and second degree outset of a vertex._{a}

Squaring a Tournament: A Proof of Dean's Conjecture, David FisherIn a "round robin tournament" each team plays every other team exactly once. Assuming no ties, for each pair of teams

iandj, eitheribeatsjorjbeatsi, but not both.

Therefore, atournamentTis an oriented graph where either (v,_{i}v) ∈_{j}Tor (v,_{j}v) ∈_{i}T, but not both. This special case of SSNC is also known asDean's Conjecture. Dean and Latka [1] verified the conjecture for tournaments whose minimum out-degree is five or less. They also verified the conjecture for regular and almost regular tournaments.

In his articleSquaring a Tournament: A Proof of Dean's Conjecture, David Fisher proves Dean's Conjecture for all possible tournaments. To this end, he introduces a (probability) densityfon an oriented graphD: each vertex gets a non-negative value in such a way that the sum of all values is 1. (Let the probability of a set be the sum of the probability of its members.) A densitywis winning ifw(I(_{D}v)) ≥_{i}w(O(_{D}v)) for all vertices_{i}v, where_{i}Iis the set of vertices that beat_{D}vand_{i}Ois the set of vertices that_{D}vbeats. In other words: for any node_{i}v, a random vertex picked from a winning density is at least as likely to beat_{i}vas it is to lose to_{i}v._{i}

Now the question rises: do all oriented graphs have winning densities? To confirm this question, Fisher gives a – in my opinion – beautiful proof using Farkas' Lemma. This lemma is primarily used in linear programming and therefore it is quite fascinating for Fisher to use it here. A simple corollary of the fact that every oriented graph has a winning densitywis that every oriented graph has a losing densityl, too. (For a losing densityl(I(_{D}v)) ≤_{i}l(O(_{D}v)) holds for all vertices_{i}v.)_{i}

What follows in Fisher's proof is a short analytical proof which is easy to understand. Fisher makes use of two lemmata. One of them does not generalise from tournaments toalloriented graphs and that is why Fisher's method cannot prove SSNC in general.

References:

[1] N. Dean and B. Latka, Squaring a tournament – an open problem,Congre. Numer.,109(1995), 73–80.

N.B.: Frédéric Havet and Stéphan Thomassé prove Dean's Conjecture in an even shorter way, using so-called median orders of tournaments. Their method has several other applications in graph theory (not necessarily of any importance to SSNC). A summary of their articleMedian Orders of Tournaments: A Tool for the Second Neighborhood Problem and Sumner's Conjecturecan be found here.

Variations on Seymour's Conjecture, Kelly Anderson, Catherine Nightingale, and Monique RichardsonAnderson, Nightingale, and Richardson verify SSNC for six different families of oriented graphs:

Finally, the three authors of the article show that if SSNC holds for strong oriented graphs, then it holds for all oriented graphs.

Acyclic directed graphs:An acyclic directed graphis a directed graph containing no cycles.

It is proven that in any acyclic directed graph, there exists a vertex with out-degree 0. To finish the proof of SSNC for acyclic directed graphs is mere child's play.Cayley graphs with additive generators:The infinite Cayley line with additive generatorsis a directed graph determined by a set of generators Γ = {g,_{1}g,..._{2}g}, where_{k}gis an integer and 0 ∉ Γ. The vertices of the graph correspond to the elements of the integers, and whenever_{i}g+_{i}a=b(whereaandbare integers), an edge is drawn fromatob.

In the article it is proven that all vertices in an infinite Cayley line with additive generators satisfy SSNC.

ACayley graph modulo,n, is defined for a subset Γ ofC(Γ,n)V= {0,1,2,...,n- 1} as being the directed graph with vertex setV, in which there is an edge fromutou+eif and only ife∈ Γ.Out-regular directed graphs:SSNC is proven for k-out regular oriented graphs fork< 4. The proofs fork= 1 andk= 2 are not hard to understand. Fork= 3 andk= 4, several cases are considered, such that the union of the cases form the complete proof. The authors of the article believe that similar types of arguments as used for the 3-out-regular and 4-out-regular oriented graphs will work to prove the conjecture that SSNC holds for all out-regular oriented graphs.k-out-regular bipartite graphs:An oriented bipartite graphis a directed graph whose vertex set can be partitioned into two disjoint, independent sets called partite sets.

An easy argument shows that all vertices of everyk-out-regular oriented bipartite graph satisfy SSNC.Pinwheel graphs:denotes the complete graph on a vertex set {1,2,...,K_{n}n}. Theline graphof a graphL(G)Gis a graph whose vertex set is the edge set ofG. Two vertices ofL(G) are adjacent if the corresponding edges share a vertex inG. Atriplet in, the line graph ofL(K_{n})K_{n}, is the subgraph induced by three verticesab,acandbc, wherea,b,c∈ {1,2,...,n}.denotes aPWC_{n}pinwheel graph, which is a directed line graph of the clique onnelements where every triplet forms a directed 3-cycle.

It is not hard to see that the out-degree of a random vertexuvis equal ton- 2 and thatn- 2 is less than or equal to the numbers of vertices at distance two of this vertexuv. Hence, all vertices in any pinwheel graphPWC_{n}satisfy SSNC.Cartesian products of directed graphs:The Cartesian productof directed graphsGandH, writtenG⊗H, is the graph with vertex setV(G) ×V(H) specified by putting an edge from (u,v) to (u',v') (where (u,v), (u',v') ∈G⊗H) if and only if (1)u=u'andvv'∈E(H), or (2)v=v'anduu'∈E(G).GandHare known as thefactor graphsof the Cartesian product.

Anderson, Nightingale, and Richardson prove that if both factor graphs of a Cartesian product each have at least one vertex that satisfies SSNC, there will be at least one vertex in the Cartesian product which satisfies SSNC.

N.B.: The notation for a Cartesian product,G⊗H, is my own notation. Anderson, Nightingale, and Richardson use a square in their article, but if I used that same symbol on this website, people might get the wrong impression that their computer cannot recognise the symbol.