Transitive partitions in realizations of tournament score sequences
Arthur H. Busch, Guantao Chen, Michael S. Jacobson · Journal of Graph Theory · 2009
Abstract A tournament is an oriented complete graph, and one containing no directed cycles is called transitive. A tournament T=(V, A) is called m‐partition transitive if there is a partition such that the subtournaments induced by each Xi are all transitive, and T is m‐partition k‐transitive if max|Xi|=k. Two tournaments are equivalent if they have the same out‐degree sequence. We show that for any m and k, T is equivalent to an m‐partition k‐transitive tournament T′ whenever T is equivalent to any tournament which contains a transitive subtournament of order at least k. This generalizes results of Guiduli et al. and Acosta et al., who proved the claim for m=2 and k=⌈n/2⌉, and m>2 and k⩽⌈n/2⌉, respectively. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 52–62, 2010