Premium
Transitive partitions in realizations of tournament score sequences
Author(s) -
Busch Arthur H.,
Chen Guantao,
Jacobson Michael S.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20438
Subject(s) - tournament , transitive relation , combinatorics , mathematics , partition (number theory) , graph , discrete mathematics
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 \documentclass{article}\usepackage{amssymb} \usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty} \begin{document}${{V}}={{X}}_{{{1}}} {\cup\hskip-8.5pt{\cdot}\hskip4pt} {{X}}_{{{2}}} {\cup\hskip-8.5pt{\cdot}\hskip4pt} \ldots {\cup\hskip-8.5pt{\cdot}\hskip4pt}{{X}}_{{{m}}}$\end{document} such that the subtournaments induced by each X i are all transitive, and T is m ‐ partition k ‐ transitive if max| X i |= 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