×

The interchange graphs of tournaments with minimum score vectors are exactly hypercubes. (English) Zbl 1207.05068

Summary: A \(\Delta \)-interchange is a transformation which reverses the orientations of the arcs in a 3-cycle of a digraph. Let \({\mathcal{T}}(S)\) be the collection of tournaments that realize a given score vector \(S\). An interchange graph of \(S\), denoted by \(G(S)\), is an undirected graph whose vertices are the tournaments in \({\mathcal{T}}(S)\) and an edge joining tournaments \(T, T' \in {\mathcal{T}}(S)\) provided \(T'\) can be obtained from \(T\) by a \(\Delta\)-interchange. In this paper, we find a set of score vectors of tournaments for which the corresponding interchange graphs are hypercubes.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brualdi, R.A., Li, Q.: The interchange graph of tournaments with the same score vector. In: Bondy, J.A., Murty, U.S.R., (eds.), Progress in Graph Theory. (Academic Press, Toronto, 1984) pp. 128–151 · Zbl 0553.05039
[2] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Boston (2005) · Zbl 1096.05001
[3] Gibson, P.M.: A bound for the number of tournaments with specified scores. J. Comb. Theory, Ser. B 36, 240–243 (1984) · Zbl 0541.05031
[4] Harary, F., Moser, L.: The theory of round robin tournaments. Amer. Math. Monthly 73, 231–246 (1966) · Zbl 0142.41602
[5] Kannan, R., Tetali, P., Vempala, S.: Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Struct. Algorithms 14, 293–308 (1999) · Zbl 0933.05145
[6] Landau H.G.: On dominance relations and the structure of animal societies, III: the condition for a score structure. Bull. Math. Biol. 15, 143–148 (1953)
[7] Lovász, L.: Combinatorial Problems and Exercises, 2nd edition. North-Holland, Amsterdam, (1993) · Zbl 0785.05001
[8] McShine, L.: Random sampling of labeled tournaments. Electron. J. Comb. 7(1), #R8 (2000) · Zbl 0954.65004
[9] Moon, J. W.: Topics on Tournaments. Holt, Rinehart and Winston, New York (1968) · Zbl 0191.22701
[10] Saad, Y., Schultz, M.H.: Topological properties of hypercubes. IEEE Trans. Comput. 37, 867–872 (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.