# Vertex-Disjoint Subtournaments of Prescribed Minimum Outdegree or Minimum Semidegree: Proof for Tournaments of a Conjecture of Stiebitz

Authors: Nicolas Lichiardopol
Journal: International Journal of Combinatorics
 (2012)

---

## Abstract

It was proved (Bessy et al., 2010) that forr≥1, a tournament with minimum semidegree at least 2r−1 contains at least r vertex-disjoint directed triangles. It was also proved (Lichiardopol, 2010) that for  integers q≥3 and r≥1, every tournament with minimum semidegree at least (q−1)r−1 contains at least r vertex-disjoint directed cycles of length q. None information was given on these directed cycles. In this paper, we fill a little this gap. Namely, we prove that for d≥1 and r≥1, every tournament of minimum outdegree at least ((d2+3d+2)/2)r−(d2+d+2)/2 contains at least r vertex-disjoint strongly connected subtournaments of minimum outdegree d. Next, we prove for tournaments a conjecture of Stiebitz stating that for integers s≥1 and t≥1, there exists a least number f(s,t) such that every digraph with minimum outdegree at least f(s,t) can be vertex-partitioned into two sets inducing subdigraphs with minimum outdegree at least s and at least t, respectively. Similar results related to the semidegree will be given. All these results are consequences of two results concerning the maximum order of a tournament of minimum outdegree d (of minimum semidegree d) not containing proper subtournaments of minimum outdegree d (of minimum semidegree d).


---

## Body

## 1. Introduction and Definitions

The definitions which follow are those of [1].LetD be a digraph. V(D) is the vertex set of D and the order of D is the cardinality of V(D). 𝒜(D) is the set of the arcs of T. Two vertices x and y of D are adjacent, if at least one of the ordered pairs (x,y) and (y,x) is an arc of D. We say that a vertex y is an outneighbor of a vertex x (inneighbour of x) if (x,y) (resp. (y,x)) is an arc of D. ND+(x) is the set of the outneighbors of x and ND-(x) is the set of the in-neighbors of x. The cardinality of ND+(x) is the outdegree dD+(x) of x and the cardinality of ND-(x) is the indegree dD-(x) of x. When no confusion is possible, we omit the subscript D. We denote by δ+(D) the minimum outdegree of D and by δ-(D) the minimum indegree of D. The minimum semidegree of D is δ0(D)=min{δ+(D),δ-(D)}.An oriented graph, is a digraphD such that for any two distinct vertices x and y of D, at most one of the couples (x,y) and (y,x) is an arc of D.A tournament is an oriented graphT such that any two distinct vertices x and y of T are adjacent. If A and B are subsets of V(T), an arc from A to B is an arc (x,y) with x∈A and y∈B. We denote by a(A,B) the number of the arcs from A to B.It is known and easy to prove that ifn is the order of T, then n≥2δ0(T)+1 and δ0(T)≤d+(x)≤n-1-δ0(T) for every vertex x of T.For a subsetS of V(T), T[S] is the subtournament induced by the vertices of S. For a vertex x of T, T-x is the subtournament induced by the vertices of T distinct from x.Ford≥1, a regular tournament of degree d is a tournament T with dT+(x)=dT-(x)=d for every vertex x of T. It is known and easy to prove that the order of T is 2d+1.A path or a cycle of a tournamentT always means a directed path or a directed cycle of T and disjoint cycles means vertex-disjoint cycles. A triangle is a directed cycle consisting of three verticesFor distinct verticesx and y of T, an (x,y)-path is a directed path starting from x and ending at y. The tournament T is said to be strongly connected, or briefly strong, if for any distinct vertices x and y, there exists an (x,y)-path. It is well known (Camion Theorem) that a tournament T is strong if and only if it contains a Hamiltonian cycle. The strong connectivity of T is the smallest nonnegative integer k(T) such that there exists a subset of k(T) vertices of V(T) disconnecting T. For k≥1, a k-strong tournament is a tournament of strong connectivity at least k.IfV1 and V2 are two vertex-disjoint subsets of V(T), we say that V1 dominates V2, if for every pair {x,y} with x∈V1 and y∈V2, (x,y) is an arc of T (which means that there is no arc from V2 to V1). If T1 and T2 are two tournaments with disjoint vertex sets, T1→T2 is the tournament whose vertex set is V(T1)∪V(T2) and whose arcs are those of T1 and T2 and the ordered pairs (x,y) with x∈V(T1) and y∈V(T2). It is known and easy to prove that a tournament T is nonstrong if and only if there exists a partition A,B of V(T) such that T=T[A]→T[B].A minimum outdegree minimal tournament is a tournament T such that every proper subtournament of T has minimum outdegree at most δ+(T)-1. If δ+(T)=d, we say that T is a minimum outdegree d minimal tournament. Similarly, one can define the notion of minimum indegree minimal tournament. A minimum semidegree minimal tournament is a tournament T such that every proper subtournament of T has minimum semidegree at most δ0(T)-1. If δ0(T)=d, we say that T is a minimum semidegree d minimal tournament.In a recent paper, Bessy et al. (see [2]) proved that for r≥1, a tournament with minimum outdegree and minimum indegree both greater or equal to 2r-1 contains at least r vertex-disjoint directed triangles. In a more recent paper (see [3]), the author generalized this result, by proving that for given integers q≥3 and r≥1, every tournament with minimum outdegree and minimum indegree both greater or equal to (q-1)r-1 contains at least r vertex-disjoint directed cycles of length q. None information was given on these directed cycles. In this paper, we fill a little this gap. More precisely, we prove:Theorem 1.1.
Ford≥2 and for r≥1, every tournament T of minimum outdegree at least ((d2+3d+2)/2)r-(d2+d+2)/2 contains at least r vertex-disjoint strong subtournaments of minimum outdegree d.Concerning the minimum semidegree, we prove the following.Theorem 1.2.
Ford≥2 and for r≥1, every tournament T of minimum semidegree at least (d2+3d+2)r-d2-2d-2 contains at least r vertex-disjoint subtournaments of minimum semidegree d.In [4], Stiebitz proposed the following conjecture.Conjecture 1.
For given integerss≥1 and t≥1, there exists a least number f(s,t) such that the vertices of any simple digraph with minimum outdegree at least f(s,t) can be partitioned into two sets inducing subdigraphs with minimum outdegree at least s and at least t, respectively.A natural generalization given by Alon (Problem 1 in [5]) is as follows.Conjecture 2.
For an integerk≥2 and for given positive integers d1,…dk, there exists a least number F(d1,…dk) such that the vertices of any simple digraph D with minimum outdegree at least F(d1,…dk) can be partitioned into k sets V1,…Vk such that δ+(D[Vi])≥di for 1≤i≤k.It is easy to prove by induction that the existence off(s,t) implies the existence of F(d1,…dk). In this paper, we prove that Stiebitz's conjecture is true for tournaments (with a supplementary constraint), namely, we prove the following.Theorem 1.3.
For given integerss≥1 and t≥1, the vertices of any tournament T with minimum outdegree at least (s2+3s+2)/2+t can be partitioned into two sets inducing subtournaments T1 and T2 with T1 strongly connected and of minimum outdegree at least s and with T2 of minimum outdegree at least t.This result will allow us to prove, for tournaments, the generalized conjecture of Stiebitz. Relatively to the minimum semidegree, we state the following.Theorem 1.4.
For given integerss≥1 and t≥1, the vertices of any tournament T with minimum semidegree at least s2+3s+2+t can be partitioned into two sets inducing subtournaments T1 and T2 with T1 of minimum semidegree at least s and with T2 of minimum semidegree at least t.Here also, a generalization is possible.


## 2. Results on Minimum Outdegree and Minimum Semidegree Minimal Tournaments

We begin with the following theorem,Theorem 2.1.
Ford≥1, any minimum outdegree d minimal tournament, is strong.Proof.
Suppose the opposite. Then there exists a partition(A,B) of V(T) such that A dominates B. Then T[B] is a proper subtournament of T of minimum outdegree at least d, which is impossible.We continue with the following,Theorem 2.2.
Ford≥1, any tournament of minimum outdegree at least d contains a minimum outdegree d minimal subtournament.Proof.
Lets be the smallest order of the subtournaments of T having minimum outdegree at least d. There exists a subtournament T′ of T of order s and of minimum outdegree at least d. Clearly, T′ is a minimum outdegree d minimal subtournament.Concerning the order of a minimum outdegreed minimal tournament, we state the following,Theorem 2.3.
Ford≥1, if T is a minimum outdegree d minimal tournament of order n, one has n≤(d2+3d+2)/2.Proof.
LetM be the set of the vertices of T of outdegree d and let m be its cardinality. For every vertex x of T, the tournament T-x has minimum outdegree d-1, and this means that x has at least one in-neighbor in M. Then, the number of the arcs from M to V(T)∖M is at least n-m. On the other hand, the number of the arcs from M to V(T)∖M is exactly md-(m(m-1))/2. It follows md-(m(m-1))/2≥n-m, hence m2-(2d+3)m+2n≤0. This implies (2d+3)2-8n≥0, hence n≤(2d+3)2/8 and since n is an integer, we get n≤((2d+3)2-1)/8, that is n≤(d2+3d+2)/2.We note that(2d+3-(2d+3)2-8n)/2≤m≤(2d+3-(2d+3)2-8n)/2. When d=2, we get n≤6. It is easy to prove that there are four minimum outdegree 2 minimal tournaments: the regular tournament T1 of order 5 (Figure 1), and three nonisomorphic tournaments T2, T3, and T4 of order 6 (Figure 2). The outdegree sequence of T2 is (2,2,2,3,3,3), and the outdegree sequence of the tournaments T3 and T4 is (2,2,2,2,3,4). We observe that T3 and T4 are not 2-connected (the two others yes).Figure 1
Minimum outdegree 2 minimal tournamentT1.Figure 2
Minimum outdegree 2 minimal tournamentsT2, T3, and T4.We claim that for every integerd≥1 the bound of Theorem 2.3 is reached. To be more precise, we claim that for every integer d≥1, there exists a minimum outdegree d minimal tournament of order (d2+3d+2)/2 and of strong connectivity 1. We are going to prove this, by induction on d.   Clearly, the assertion is true for d=1. Suppose that the assertion is true up to the row d-1, d≥2. Let then Td-1 be a minimum outdegree d-1 minimal tournament of order ((d-1)2+3(d-1)+2)/2=(d2+d)/2. Let Td be the tournament defined as follows.(i)
The vertices ofTd are the vertices of Td-1 and d+1 additional vertices x and y1,y2,…,yd.(ii)
The arcs ofTd are the arcs of Td-1, the couples (x,yi), 1≤i≤d, the couples (z,x) with z∈V(Td-1), the couples (yi,z) with 1≤i≤d and z∈V(Td-1) and the arcs of an arbitrary tournament with A={y1,…,yd} as vertex set. It is easy to see that Td is a minimum outdegree d minimal tournament of order (d2+d)/2+d+1=(d2+3d+2)/2 and of strong connectivity 1 (because x disconnects Td). So the assertion is true for d and consequently the result is proved.In fact, there are minimum outdegreed minimal tournaments of strong connectivity 1 of order smaller than (d2+3d+2)/2. Indeed, if we take a regular tournament of degree d-1, with the above construction, we get a minimum outdegree d minimal tournament of connectivity 1 and of order 2(d-1)+1+d+1=3d. We think that 3d is the minimum order of a minimum outdegree d minimal tournament of connectivity 1.Byminimum outdegreedcritical tournament, we mean a tournament T of minimum outdegree d such that for every vertex x of T, the tournament T-x has minimum out degree d-1. It is clear that a minimum outdegree d minimal tournament is minimum outdegree critical. By the way, we observe that in the proof of Theorem 2.3, we use only the fact that T is minimum outdegree d critical and as the obtained upper bound is reached, another proof using the fact that T is minimum outdegree d minimal cannot improve this upper bound. However, we claim that for d≥3, the notion of minimum outdegree d minimal tournament does not coincide with the notion of minimum outdegree d critical tournament. Indeed, let T′ be a regular tournament of degree d and consider a vertex x of T′. We define the tournament T in the following way.(i)
The vertices ofT are the vertices of T′ and the additional vertices a, b and c of a directed triangle Δ.(ii)
V(Δ) is dominated by NT′+(x), x is dominated by V(Δ). To each vertex of V(Δ) we join exactly d-2 outneighbors in NT′-(x) so that every vertex of NT′-(x) has at least one in-neighbor in V(Δ) (this is possible when d≥3).T has minimum outdegree d and the vertices x,a,b, and c are of outdegree d. It is easy to see that every vertex of T is dominated by a vertex of {x,a,b,c}. This means that T is minimum outdegree d critical. Manifestly, since T′ is a proper subtournament of T of minimum outdegree d, T is not minimum outdegree d minimal. This corroborates our statement. However, as for minimum outdegree minimal tournaments, we have the following.Theorem 2.4.
Ford≥1, any critically outdegree d tournament T is strong.Proof.
Suppose the opposite. Then there exists a partition(A,B) of V(T) such that A dominates B. Then T[B] is a tournament of minimum outdegree at least d, which implies |B|≥2d+1>d. Consider a vertex x of A. An in-neighbor of x is in A and then its outdegree is greater than d. This means that T-x is a tournament of minimum outdegree d, which is not possible. Consequently T is strong.For minimum semidegree minimal tournaments, the situation is a little different. Already, we observe that a minimum semidegree minimal tournament is not necessarily strong. Indeed, ifT1 is a minimum indegree d minimal tournament and if T2 is a a minimum outdegree d minimal tournament, vertex disjoint with T1, it is easy to prove that T1→T2 is a nonstrong minimum semidegree d minimal tournament. As for Theorem 2.2, we have the following.Theorem 2.5.
Ford≥1, any tournament of minimum semidegree at least d contains a minimum semidegree d minimal subtournament.Proof.
Lets be the smallest order of the subtournaments of T having minimum semidegree at least d. There exists a subtournament T′ of T of order s and of minimum semidegree at least d. Clearly, T′ is a minimum semidegree d minimal subtournament.As regards the maximum order, we state the following.Theorem 2.6.
Ford≥2, if T is a minimum semidegree d minimal tournament of order n and of minimum semidegree d, we have n≤d2+3d+2.Proof.
We haven≥2d+1 and if n=2d+1, the theorem is proved. So, we may suppose n>2d+1. For every vertex x of T, the tournament T-x has minimum semidegree d-1. This means that x has an in-neighbor of outdegree d or an outneighbor of indegree d (here “or” is not exclusive). Denote by M1 the set of the vertices of T of outdegree d and by M2 the set of the vertices of T of indegree d. Since n>2d+1, M1 and M2 are disjoint. Let m1 and m2 be the cardinalities of the sets M1 and M2. If m1=0 or if m2=0, as in the proof of Theorem 2.3, we get n≤(d2+3d+2)/2 and then the theorem is proved. So, we may suppose m1≥1 and m2≥1. Denote by M3 the set of the vertices of T not in M1∪M2 and having at least one in-neighbor in M1, and by m3 the cardinality of M3. Let M4=V(T)∖(M1∪M2∪M3) and m4=|M4|. Every possible vertex of M4 has a least one outneighbor in M2.
We havea(M1,M3)≥m3, and since a(M1,M3)=m1d-(m1(m1-1))/2-a(M1,M2)-a(M1,M4), it follows that
(2.1)m1d-m1(m1-1)2-a(M1,M2)-a(M1,M4)≥m3.
Similarly, we get
(2.2)m2d-m2(m2-1)2-a(M1,M2)-a(M3,M2)≥m4.
From (2.1) and (2.2), we get by addition (m1+m2)d+(m1+m2)/2-(m12+m22)/2-2a(M1,M2)-a(M1,M4)-a(M3,M2)≥n-m1-m2. It is easy to prove that m12+m22≥(m1+m2)2/2. It follows (m1+m2)(d+(1/2))-(m1+m2)2/4-2a(M1,M2)-a(M1,M4)-a(M3,M2)≥n-(m1+m2), hence (m1+m2)(d+(1/2))-(m1+m2)2/4≥n-(m1+m2). This yields (m1+m2)2-(4d+6)(m1+m2)+4n≤0. This implies (2d+3)2-4n≥0, hence n≤(2d+3)2/4 and since n is an integer, we get n≤((2d+3)2-1)/4, that is n≤d2+3d+2.Concerning the numberm1+m2 of the vertices x of T with either outdegree d or indegree d, we have 2d+3-(2d+3)2-4n≤m1+m2≤2d+3-(2d+3)2-4n. When d=2, we get n≤12, and this bound is reached. Indeed if T1 is a critically indegree d tournament of order 6 and if T2 is a a critically outdegree d tournament of order 6, then T1→T2 is a critically semidegree d tournament of order 6.


## 3. Proofs of Theorems1.1 and 1.2

### 3.1. Proof of Theorem1.1

Sinceδ+(T)≥d, by Theorem 2.2, T contains minimum outdegree d minimal subtournaments. Let s>0 be the maximum number of vertex-disjoint minimum outdegree d minimal subtournaments. Then there exist s vertex-disjoint minimum outdegree d minimal subtournaments T1,…TS, and by Theorem 2.3, these tournaments cover a set S with at most ((d2+3d+2)/2)s vertices of T. Suppose that s<r. A vertex x of V(T)∖S has at most ((d2+3d+2)/2)s outneighbors in S. It follows that x has at least ((d2+3d+2)/2)r-(d2+d+2)/2-((d2+3d+2)/2)s≥d outneighbors in V(T)∖S. This means that the subtournament induced by V(T)∖S has minimum outdegree at least d and then by Theorem 2.2, it contains a minimum outdegree d minimal subtournament. But by maximality of s, this is not possible. Consequently s≥r and therefore T contains r minimum outdegree d minimal subtournaments. Since these tournaments are strong (Theorem 2.1), the result is proved.


### 3.2. Proof of Theorem1.2

Sinceδ0(T)≥d, by Theorem 2.4, T contains minimum semidegree d minimal subtournaments. Let s>0 be the maximum number of vertex-disjoint minimum semidegree d minimal subtournaments. Then there exist s vertex-disjoint minimum semidegree d minimal subtournaments, and by Theorem 2.5, these tournaments cover a set S with at most (d2+3d+2)s vertices of T. Suppose that s<r. A vertex x of V(T)∖S has at most (d2+3d+2)s outneighbors in S and at most (d2+3d+2)s in-neighbors in S. It follows that x has at least (d2+3d+2)r-d2-2d-2-(d2+3d+2)s≥d outneighbors in V(T)∖S and at least (d2+3d+2)r-d2-2d-2-(d2+3d+2)s≥d in-neighbors in V(T)∖S. This means that the subtournament induced by V(T)∖S has minimum semidegree at least d and then by Theorem 2.4, it contains a minimum semidegree d minimal subtournament. But by maximality of s, this is not possible. Consequently s≥r and therefore T contains r minimum semidegree d minimal subtournaments, which proves the result.


## 3.1. Proof of Theorem1.1

Sinceδ+(T)≥d, by Theorem 2.2, T contains minimum outdegree d minimal subtournaments. Let s>0 be the maximum number of vertex-disjoint minimum outdegree d minimal subtournaments. Then there exist s vertex-disjoint minimum outdegree d minimal subtournaments T1,…TS, and by Theorem 2.3, these tournaments cover a set S with at most ((d2+3d+2)/2)s vertices of T. Suppose that s<r. A vertex x of V(T)∖S has at most ((d2+3d+2)/2)s outneighbors in S. It follows that x has at least ((d2+3d+2)/2)r-(d2+d+2)/2-((d2+3d+2)/2)s≥d outneighbors in V(T)∖S. This means that the subtournament induced by V(T)∖S has minimum outdegree at least d and then by Theorem 2.2, it contains a minimum outdegree d minimal subtournament. But by maximality of s, this is not possible. Consequently s≥r and therefore T contains r minimum outdegree d minimal subtournaments. Since these tournaments are strong (Theorem 2.1), the result is proved.


## 3.2. Proof of Theorem1.2

Sinceδ0(T)≥d, by Theorem 2.4, T contains minimum semidegree d minimal subtournaments. Let s>0 be the maximum number of vertex-disjoint minimum semidegree d minimal subtournaments. Then there exist s vertex-disjoint minimum semidegree d minimal subtournaments, and by Theorem 2.5, these tournaments cover a set S with at most (d2+3d+2)s vertices of T. Suppose that s<r. A vertex x of V(T)∖S has at most (d2+3d+2)s outneighbors in S and at most (d2+3d+2)s in-neighbors in S. It follows that x has at least (d2+3d+2)r-d2-2d-2-(d2+3d+2)s≥d outneighbors in V(T)∖S and at least (d2+3d+2)r-d2-2d-2-(d2+3d+2)s≥d in-neighbors in V(T)∖S. This means that the subtournament induced by V(T)∖S has minimum semidegree at least d and then by Theorem 2.4, it contains a minimum semidegree d minimal subtournament. But by maximality of s, this is not possible. Consequently s≥r and therefore T contains r minimum semidegree d minimal subtournaments, which proves the result.


## 4. Proofs of Theorems1.3 and 1.4 and Generalizations

Since the proof of Theorem1.4 is similar to that of Theorem 1.3, we prove only Theorem 1.3.By Theorem2.2, T contains a minimum outdegree s minimal subtournament T1, which is strong by Theorem 2.1. By Theorem 2.3, the order of T1 is at most (s2+3s+2)/2. Let T2 be the subtournament induced by V(T)∖V(T1). A vertex x of T2 has at least (s2+3s+2)/2+t outneighbors in V(T) and at most (s2+3s+2)/2 outneighbors in V(T1). It follows that x has at least t outneighbors in V(T2). This means that T2 has minimum outdegree at least t, and consequently the theorem is proved.This being established, an easy induction, gives the following.Theorem 4.1.
For an integerk≥2 and for given positive integers d1,…dk, the vertices of any tournament T with minimum outdegree at least (d12+3d1+2)/2+⋯+(dk-12+3dk-1+2)/2+dk, can be partitioned into k sets V1,…,Vk so that δ+(T[Vi])≥di for 1≤i≤k and T[Vi] is strong for 1≤i≤k-1.Proof.
The assertion is true fork=2 because it is Theorem 1.3. Suppose that the assertion is true up to the row k-1, k≥3 and let us study for k. So, let T be a tournament with minimum outdegree at least (d12+3d1+2)/2+⋯+(dk-12+3dk-1+2)/2+dk. By Theorem 1.3, V(T) can be partitioned into two sets V1 and V′, so that T[V1] is strong, of minimum outdegree at least d1 and T′=T[V′] is of minimum out degree at least (d22+3d2+2)/2+⋯+(dk-12+3dk-1+2)/2+dk. By induction hypothesis V(T′)=V′ can be partitioned into k-1 sets V2,…,Vk so that T′[Vi]=T[Vi] is of minimum outdegree at least di for 2≤i≤k and T′[Vi]=T[Vi] is strong for 2≤i≤k-1. It follows, by considering also V1, that the assertion is true for k and therefore the result is proved.In fact, we are able to prove Conjecture1 (and then Conjecture 2) for a larger class of oriented graphs (including tournaments). Namely, we state the following.Theorem 4.2.
For given integerss≥1, t≥1 and r≥0, let D be an oriented graph with minimum outdegree at least ((s+r)2+3(s+r)+2)/2+t+r and such that for every vertex x there exist at most r vertices of D nonadjacent with x. Then the vertices of D can be partitioned into two sets inducing oriented graphs D1 and D2 with D1 of minimum outdegree at least s, and strongly connected when r=0, and with D2 of minimum outdegree at least t.Proof.
Whenr=0, D is a tournament and then the result is proved. Therefore we may suppose r≥1. By orienting every nonedge of D, we obtain a tournament T having D as spanning subdigraph. Since T has minimum out degree at least ((s+r)2+3(s+r)+2)/2+t+r, by Theorem 1.3, V(T)=V(D) can be partitioned into two sets inducing subtournaments T1 and T2 with T1 of minimum outdegree at least s+r and with T2 of minimum outdegree at least t+r. Since every vertex of V(D) has at most r outneighbors in T which are not outneighbors in D, by deleting all the arcs of T1 and T2 which are not arcs of D, we get a spanning subdigraph D1 of T1, induced in D by V(T1)=V(D1), with minimum outdegree at least s and a spanning subdigraph D2 of T2, induced in D by V(T2)=V(D2) and with minimum outdegree at least t. Since V(D1), V(D2) is a partition of V(D), the theorem is proved.For example an oriented graphD of minimum outdegree at least 34 such that every vertex is nonadjacent with at most 4 vertices is vertexdecomposable into two oriented graphs of minimum out degree 2.The proof of Theorem1.4 (related to the semidegree) is similar to that of Theorem 1.3 and here also a generalization is possible.


## 5. An Open Problem of Thomassen

In [6], Reid proposed the following problem raised by Thomassen.Problem 1.
Letrandqbe positive integers, does there exists a positive integers=s(r,q)so that all but a finite number ofs-strong tournaments can be vertex-partitioned into anr-strong and aq-strong subtournament?By minimalk-strong tournament, we mean a k-strong tournament T such that every proper subtournament of T has strongconnectivity at most k-1. By critical k-strong tournament, we mean a k-strong tournament T such that for every vertex x, the subtournament T-x has strong connectivity at most k-1. We think it is as follows.Conjecture 3.
For a given integerk>0, there exists a function  f(k) such that every minimal  k-strong tournament is of order at most  f(k).It is easy to prove that a positive answer to this conjecture would give a positive answer to Thomassen's open problem. It is known that the conjecture is false, when we replace minimalk-strong tournament by critical k-strong tournament, but in spite of that, we maintain our conjecture.



---

*Source: 273416-2011-08-03.xml*