✦ LIBER ✦

Kings in multipartite tournaments

✍ Scribed by K.M. Koh; B.P. Tan

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 584 KB
Volume: 147
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00169-j

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be an n-partite tournament and let k,(T) denote the number of r-kings of T. Gutin (1986) and Petrovic and Thomassen (1991) proved independently that if T contains at most one transmitter, then k4(T) >i 1, and found infinitely many bipartite tournaments T with at most one transmitter such that k 3 (T) = 0. In this paper, we (i) obtain some sufficient conditions for Tto have k3(T )/> 1, (ii) show that if Tcontains no transmitter, then k4(T ) >/4 when n = 2, and k4(T ) >/3 when n >/3, and (iii) characterize all Twith no transmitter such that the equalities in (ii) hold.

📜 SIMILAR VOLUMES

The number of kings in a multipartite to

The number of kings in a multipartite tournament

✍ K.M. Koh; B.P. Tan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 401 KB

We show that in any n-partite tournament, where n/> 3, with no transmitters and no 3-kings, the number of 4-kings is at least eight. All n-partite tournaments, where n/>3, having eight 4-kings and no 3-kings are completely characterized. This solves the problem proposed in Koh and Tan (accepted).

Cycles in Multipartite Tournaments

✍ Y.B. Guo; L. Volkmann 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 132 KB

On Cycles in Multipartite Tournaments

✍ G. Gutin 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Kings in semicomplete multipartite digra

Kings in semicomplete multipartite digraphs

✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

A digraph obtained by replacing each edge of a complete p-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p-partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is

Kings in bipartite tournaments

✍ Vojislav Petrovic 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 499 KB

We present a variety of results concerning characterization, number, distribution and some aspects of stability of r-kings (r = 2 4) of bipartite tournaments.

Weakly Hamiltonian-connected ordinary mu

Weakly Hamiltonian-connected ordinary multipartite tournaments

✍ Jørgen Bang-Jensen; Gregory Gutin; Jing Huang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 614 KB

We characterize weakly Hamiltonian-connected ordinary multipartite tournaments. Our result generalizes such a characterization for tournaments by Thomassen and implies a polynomial algorithm to decide the existence ofa Hamiltonian path connecting two given vertices in an ordinary multipartite tourna