Arc Reversals in Tournaments.
Claybourne Waldrop · 1978
In 196k, H.J. Ryser [27] proved that, given any two n-tournaments T,U with the same score (or outdegree) se quence, T can be transformed into (a copy of) U by suc cessively reversing the orientations of appropriately cho sen 3-cycles.In 1973, K.B. Reid [22] showed that any ntournament can be transformed into any other by successive ly reversing paths of any fixed length k , 1 ^ k <2 n-1 .Based on these results, a problem is abstracted and examined in Chapters 1 and 2. If D is a digraph and T,U are n-tournaments, T is equivalent to U via D-reversals if T can be transformed into U by successively re versing copies of D , subject to the proviso that if D is not isomorphic to its directional dual D* , we allow D*-reversals also (at any stage).An equivalence relation on n-tournaments is thereby obtained, so consider: THE REVERSAL PROBLEM.Given a digraph D , determine (preferably, characterize) the resulting equivalence classes of n-tournaments.A proof technique involving the concepts of "the di rected difference graph" and "refinement" is developed and applied to a variety of digraphs in connection with this problem, included among which are cycles, generalized k-cy-cles, paths, antidirected paths, and "claws."In most cases, characterizations of the equivalence classes in terms of simple tournament parameters are obtained, e.g., Ryser's theorem holds if "3-cycles" is replaced by "4-cycles" or by "5-cycles," and this is best possible, though partial re sults are obtained for k-cycle-reversals.In addition to these results, new proofs are supplied for those cited pre viously.Panconnectivity in tournaments is investigated in (the independent) Chapter 3. A tournament is strongly (resp., we a k l y ) panconnected if it contains paths of all possible lengths greater than two with prescribed initial and termi nal vertices (resp., prescribed endvertices).In recent work, C. Thomassen [29] has completely characterized weakly panconnected tournaments.Using this characterization, the following main result is obtained.THEOREM.An n-tournament T is strongly panconnected pro vided that n ^ max { 5q(T)+4 , 2q(T)+13 } , where q(T) is the maximum difference between the scores of T .More over, the bound is best possible whenever q(T) ^ 3 .This extends work in [1; 2; 15; and 29] by considerably broadening the class of tournaments known to be strongly panconnected.A local aspect of panconnectivity is also studied, and some results are utilized in Chapters 1 and 2. viii