ON CLAWS BELONGING TO EVERY TOURNAMENT

被引：11

作者：

LU, XY ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DEPT MATH,NEW BRUNSWICK,NJ 08903

来源：

COMBINATORICA | 1991年 / 11卷 / 02期

关键词：

AMS subject classification code (1980): 05C20;

D O I：

10.1007/BF01206360

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A directed graph is said to be n-unavoidable if it is contained as a subgraph by every tournament on n vertices. A number of theorems have been proven showing that certain graphs are n-unavoidable, the first being Redei's result that every tournament has a Hamiltonian path. M. Saks and V. Sos gave more examples in [6] and also a conjecture that states: Every directed claw on n vertices such that the outdegree of the root is at most [n/2] is n-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result: any claw of rootdegree less-than-or-equal-to n/4 is n-unavoidable.

引用

页码：173 / 179

页数：7