On avoidable and unavoidable claws

被引：9
作者：
Lu, XY
Wang, DW
Wong, CK
机构：
[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Peoples R China
[2] Acad Sinica, Inst Informat Sci, Taipei, Taiwan
来源：
DISCRETE MATHEMATICS | 1998年 / 184卷 / 1-3期
关键词：
D O I：
10.1016/S0012-365X(97)00207-0
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A claw of degree k is a directed tree consisting of k paths emerging from a common root. We prove that every claw of order n with degree less than 19/50 n appears in every n-vertex tournament. We also construct avoidable claws with degree approaching 11/23 n. Thus for large n, the maximum lambda such that every claw with degree lambda n appears in every n-vertex tournament satisfies lambda less than or equal to 11/23. This improves earlier bounds. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：259 / 265
页数：7
相关论文
共 12 条
[1]   REALIZATION OF CERTAIN GENERALIZED PATHS IN TOURNAMENTS [J].
ALSPACH, B ;
ROSENFELD, M .
DISCRETE MATHEMATICS, 1981, 34 (02) :199-202
[2]  
Erdos P., 1965, CANAD MATH B, V8, P269, DOI DOI 10.4153/CMB-1965-017-1
[3]  
GRUNBAUM B, 1971, J COMBINATORIAL TH B, V11, P249
[4]  
LANDAU H. G., 1953, BULL MATH BIOPHYS, V15, P143, DOI 10.1007/BF02476378
[5]   ON CLAWS BELONGING TO EVERY TOURNAMENT [J].
LU, XY .
COMBINATORICA, 1991, 11 (02) :173-179
[6]   CLAWS CONTAINED IN ALL N-TOURNAMENTS [J].
LU, XY .
DISCRETE MATHEMATICS, 1993, 119 (1-3) :107-111
[7]  
Lu XY, 1996, J GRAPH THEOR, V22, P335, DOI 10.1002/(SICI)1097-0118(199608)22:4<335::AID-JGT7>3.0.CO
[8]  
2-M
[9]  
Redei L., 1934, Acta Litt. Szeged, V7, P39
[10]  
Rosenfeld M., 1974, Journal of Combinatorial Theory, Series B, V16, P234, DOI 10.1016/0095-8956(74)90069-0
12