A survey of bipartite tournaments

Articles in Press

Document Type : Survey paper

Authors

1 Ball State University, Muncie, Indiana, USA

2 Purdue University Fort Wayne, Fort Wayne, Indiana, USA

Abstract

The family of mathematical objects known as tournaments constitutes one of the main areas of directed graphs, being defined as having a set of vertices in which each pair is joined by exactly one arc. Here we are interested in a secondary family known as bipartite tournaments. These are defined as having two non-empty sets of vertices and one arc joining each pair that are in different sets. There is a substantial theory of this topic also, and this article presents many of its foundational areas. One key concept is that of the number of arcs going from a vertex, called its score, and the theory involves what lists of numbers can constitute the scores. The cycles in a bipartite tournament have a variety of interesting collections involving lengths. Other fundamental concepts that we discuss include bipartite tournaments with the property of being self-converse, the efficient removal of cycles by the reversal of arcs, development of a theory of upsets, and properties of automorphism groups of the structures. The concept of bipartite tournaments also generalizes naturally to multipartite tournaments with more parts. Many of the results we discuss in this paper lead to questions about analogous extensions to these structures. In the last section of the paper, we include a discussion of further research directions.

Keywords

Main Subjects

References

[1] K. Bagga, On upsets in bipartite tournaments, pp. 37–46, John Wiley & Sons, Inc., USA, 1985.
[2] K. Bagga and L. Beineke, On superstrong bipartite tournaments, Congr. Numer. 53 (1986), 113–119.
[3] K.S. Bagga, Some structural properties of bipartite tournaments, Ph.D. thesis, Purdue University, 1984.
[4] K.S. Bagga and L.W. Beineke, Uniquely realizable score lists in bipartite tournaments, Czech. Math. J. 37 (1987), no. 2, 323–333.
[5] K.S. Bagga and L.W. Beineke, On the numbers of some subtournaments of a bipartite tournament, Ann. N.Y. Acad. Sci. 555 (1989), no. 1, 21–29.
[6] Y. Bai, B. Li, and H. Li, Vertex-disjoint cycles in bipartite tournaments, Discrete Math. 338 (2015), no. 8, 1307–1309. https://doi.org/10.1016/j.disc.2015.02.012
[7] C. Balbuena, D. González-Moreno, and M. Olsen, Vertex disjoint 4-cycles in bipartite tournaments, Discrete Math. 341 (2018), no. 4, 1103–1108.  https://doi.org/10.1016/j.disc.2017.10.023
[8] J. Bang-Jensen, G. Gutin, and J. Huang, Weakly Hamiltonian-connected ordinary multipartite tournaments, Discrete Math. 138 (1995), no. 1-3, 63–74. https://doi.org/10.1016/0012-365X(94)00188-O
[9] L. Beineke, A tour through tournaments: A comparative study of bipartite and ordinary tournaments, Combinatorics, Proceedings of the Eighth British Combinatorial Conference (H.N.V. Temperley ScD, ed.), Cambridge University Press,
1981, pp. 41–55.
[10] L. Beineke and M. Lipman, The group-universality of bipartite tournaments, Scientia: Math. Sci. 2 (1988), 11–12.
[11] J.C. Bermond and C. Thomassen, Cycles in digraphs–A survey, J. Graph Theory 5 (1981), no. 1, 1–43.
[12] B. Bollobés, O. Frank, and M. KaroĊ„Ski, On 4-cycles in random bipartite tournaments, J. Graph Theory 7 (1983), no. 2, 183–194. https://doi.org/10.1002/jgt.3190070207
[13] R.A. Brualdi and J. Shen, Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs, J. Comb. Theory B 85 (2002), no. 2, 189–196. https://doi.org/10.1006/jctb.2001.2094
[14] P. Camion, Chemins et circuits hamiltoniens des graphes complets, C.R. Hebd. Seances Acad. Sci. 249 (1959), no. 21, 2151–2152.
[15] W.J.R. Eplett, Self-converse tournaments, Can. Math. Bull. 22 (1979), no. 1, 23–27. https://doi.org/10.4153/CMB-1979-004-6
[16] R. Frucht, Herstellung von graphen mit vorgegebener abstrakter gruppe, Compos. Math. 6 (1939), 239–250.
[17] D.R. Fulkerson, Upsets in round robin tournaments, Can. J. Math. 17 (1965), 957–969. https://doi.org/10.4153/CJM-1965-091-7
[18] D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957), 1073–1082.
[19] W.D. Goddard, G. Kubicki, O.R. Oellermann, and S. Tian, On multipartite tournaments, J. Comb. Theory B 52 (1991), no. 2, 284–300.  https://doi.org/10.1016/0095-8956(91)90069-V
[20] Y. Guo and L. Volkmann, A complete solution of a problem of Bondy concerning multipartite tournaments, J. Comb. Theory B 66 (1996), no. 1, 140–145.  https://doi.org/10.1006/jctb.1996.0010
[21] G. Gutin, On cycles in multipartite tournaments, J. Comb. Theory B 58 (1993), no. 2, 319–321. https://doi.org/10.1006/jctb.1993.1047
[22] F. Harary and L. Moser, The theory of round robin tournaments, Am. Math. Mon. 73 (1966), no. 3, 231–246. https://doi.org/10.1080/00029890.1966.11970749
[23] M.A. Henning and O.R. Oellermann, The average connectivity of regular multipartite tournaments, Australas. J. Comb. 23 (2001), 101–114.
[24] M.A. Henning and A. Yeo, Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012), no. 2, 687–694. https://doi.org/10.1137/100802463
[25] A. Holtkamp and L. Volkmann, Solution of a conjecture of Vandell on decycling bipartite tournaments by deleting arcs, J. Combin. Math. Combin. Comput. 87 (2013), 3–19.
[26] B. Jackson, Cycles in bipartite graphs, J. Comb. Theory B 30 (1981), no. 3, 332–342. https://doi.org/10.1016/0095-8956(81)90050-2
[27] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981), no. 2, 145–157. https://doi.org/10.1002/jgt.3190050204
[28] K.M. Koh and B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167 (1997), 411–418.
https://doi.org/10.1016/S0012-365X(96)00244-0
[29] N. Lichiardopol, Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles, SIAM J. Discrete Math. 28 (2014), no. 3, 1618–1627.  https://doi.org/10.1137/130922653
[30] J.W. Moon, On the score sequence of an n-partite tournament, Can. Math. Bull. 5 (1962), no. 1, 51–58. https://doi.org/10.4153/CMB-1962-008-9
[31] J.W. Moon, Tournaments with a given automorphism group, Can. J. Math. 16 (1964), 485–489. https://doi.org/10.4153/CJM-1964-050-9
[32] J.W. Moon, Topics on Tournaments, Holt, Rinehart, Winston, 1968.
[33] J.W. Moon and L. Moser, On the distribution of 4-cycles in random bipartite tournaments, Can. Math. Bull. 5 (1962), no. 1, 5–12.  https://doi.org/10.4153/CMB-1962-002-0
[34] L. Redei, Ein kombinatorischer satz, Acta Litt. Szeged. 7 (1934), 39–43.
[35] K.B. Reid and L.W. Beineke, Tournaments, ch. 7, Selected Topics in Graph Theory (K.B. Reid and J. Wilson, eds.), Academic Press, 1978, pp. 169–204.
[36] H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Can. J. Math. 9 (1957), 371–377. https://doi.org/10.4153/CJM-1957-044-3
[37] M. Stob, Rankings from round-robin tournaments, Manag. Sci. 31 (1985), no. 9, 1191–1195.
[38] C. Thomassen, Hamiltonian-connected tournaments, J. Comb. Theory B 28 (1980), no. 2, 142–163. https://doi.org/10.1016/0095-8956(80)90061-1
[39] R.C. Vandell, Decycling bipartite tournaments by deleting arcs, Ars Combin. 116 (2014), 331–342.
[40] R.D.V. Vega, On the balanced case of the Brualdi-Shen conjecture on 4-cycle decompositions of Eulerian bipartite tournaments, Electron. J. Graph Theory Appl. 3 (2015), no. 2, 191–196. http://dx.doi.org/10.5614/ejgta.2015.3.2.7
[41] L. Volkmann, Strong subtournaments of multipartite tournaments, Australas. J. Comb. 20 (1999), 189–196.
[42] L. Volkmann, Multipartite tournaments: A survey, Discrete Math. 307 (2007), no. 24, 3097–3129. https://doi.org/10.1016/j.disc.2007.03.053
[43] K. Wayland, Bipartite score sets, Can. Math. Bull. 26 (1983), no. 3, 273–279. https://doi.org/10.4153/CMB-1983-044-7
[44] G.F. Zhou, K.M. Zhang, and G. Xue, Vertex-pancyclic multipartite tournaments, Nanjing Daxue Xuebao Ziran Kexue Ban 37 (2001), 477–485.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 17 July 2025

Files

Share

How to cite

Statistics