Kings in multipartite tournaments

被引:17
作者
Koh, KM [1 ]
Tan, BP [1 ]
机构
[1] NATL UNIV SINGAPORE,DEPT MATH,SINGAPORE 0511,SINGAPORE
关键词
D O I
10.1016/0012-365X(94)00169-J
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let T be an n-partite tournament and let k(r)(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 k(4)(T) greater than or equal to 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 T to have k(3)(T) greater than or equal to 1, (ii) show that if T contains no transmitter, then k(4)(T) greater than or equal to 4 when n = 2, and k(4)(T) greater than or equal to 3 when n greater than or equal to 3, and (iii) characterize all T with no transmitter such that the equalities in (ii) hold.
引用
收藏
页码:171 / 183
页数:13
相关论文
共 10 条
[1]  
BRIDGLAND MF, 1984, PROGR GRAPH THEORY, P117
[2]   ON MULTIPARTITE TOURNAMENTS [J].
GODDARD, WD ;
KUBICKI, G ;
OELLERMANN, OR ;
TIAN, S .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (02) :284-300
[3]   THE RADII OF N-PARTITE TOURNAMENTS [J].
GUTIN, GM .
MATHEMATICAL NOTES, 1986, 40 (3-4) :743-744
[4]  
LANDAU H. G., 1953, BULL MATH BIOPHYS, V15, P143, DOI 10.1007/BF02476378
[5]  
Maurer S.B., 1980, MATH MAG, V53, P67, DOI [DOI 10.1080/0025570X.1980.11976831, DOI 10.1080/0025570X.1980.11976837]
[6]  
MOON JW, 1962, MATH MAG, V35, P189
[7]   KINGS IN K-PARTITE TOURNAMENTS [J].
PETROVIC, V ;
THOMASSEN, C .
DISCRETE MATHEMATICS, 1991, 98 (03) :237-238
[8]  
PETROVIC V, UNPUB KINGS BIPARTIT
[9]   EVERY VERTEX A KING [J].
REID, KB .
DISCRETE MATHEMATICS, 1982, 38 (01) :93-98
[10]  
SILVERMAN DL, 1962, MATH MAG, V35, P189