Home » Subject » Graph Theory » Directed Graphs » Tournaments

Partitionning a tournament into k-strongly connected subtournaments.

Importance: Medium ✭✭
Author(s): Thomassen, Carsten
Subject: Graph Theory
» Directed Graphs
» » Tournaments
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 15th, 2013
Problem   Let $ k_1, \dots , k_p $ be positve integer Does there exists an integer $ g(k_1, \dots , k_p) $ such that every $ g(k_1, \dots , k_p) $-strong tournament $ T $ admits a partition $ (V_1\dots , V_p) $ of its vertex set such that the subtournament induced by $ V_i $ is a non-trivial $ k_i $-strong for all $ 1\leq i\leq p $.

If $ k_i=1 $ for $ 2\leq k_i\leq k_p $, then $ g(k_1, \dots , k_p) $ exists and is at most $ k_1+3p-3 $. This follows by an easy induction on $ p $, by taking $ V_p $ to be a set inducing a directed $ 3 $-cycle.

The following example shows that if it exists $ g(k_1, \dots , k_p)\geq k_1+\cdots + k_p $. Set $ s=k_1 + \cdots + k_p -1 $. For $ n\geq 3s $, let $ R_s(n) $ be a tournament on $ n $ vertices having a set $ R $ of $ s $ vertices such that $ T-R $ a transitive tournament of order $ n-s $ with hamiltonian path $ (v_1,\dots , v_{n-s}) $, and $ R $ dominates $ \{v_1, \dots , v_{s}\} $ and is dominated by $ \{v_{n-2s+1}, \dots , v_{n-s}\} $. It easy to check that $ R_s(n) $ is $ s $-strongly connected. However, every (non-trivial) $ k $-strong tournament of $ R_s(n) $ must contain at least $ k $ vertices of $ R $. Hence $ R_s(n) $ does not have a partition $ (V_1\dots , V_p) $ of its vertex set such that the subtournament induced by $ V_i $ is a non-trivial $ k_i $-strong for all $ 1\leq i\leq p $.

Some small examples give better lower bound. For example, the Paley tournament on 7 vertices which is 3-strong cannot be partionned into two strong subtournaments. However, there are only finitely many known such tournaments. Chen, Gould, and Li [CGL] showed that every $ k $-strongly connected tournament with at least $ 8k $ vertices has a partition into $ k $ strongly connected tournaments.

The existence of $ g(2,2) $ is still open.

Bibliography

[CGL] G. Chen, R.J. Gould, and H. Li, Partitioning vertices of a tournament into independent cycles, J. combin. Theory Ser B, Vol 83, no. 2 (2001) 213-220.

*[R] K.B. Reid, Three problems on tournaments, Graph Theory and Its Applications, East. and West. Ann. New York Acad. Sci. 576 (1989), 466-473.


* indicates original appearance(s) of problem.
add new comment