|
|||||
|
|
Largest digraphs contained in alln-tournaments |
|
| Authors: | N. Linial M. Saks Vera T. Sós |
| Affiliation: | 1. Institute of Mathematics and Computer Science Hebrew University, 91904, Jerusalem, Israel 2. Department of Mathematics, Rutgers University, 08903, New Brunswick, N. J., USA 3. Department of Analysis I., E?tv?s University, H-1088, Budapest, Hungary |
| Abstract: | Letf(n) (resp.g(n)) be the largestm such that there is a digraph (resp. a spanning weakly connected digraph) onn-vertices andm edges which is a subgraph of every tournament onn-vertices. We prove that $$nlog _2 n - c_1 n geqq f(n) geqq g(n) geqq nlog _2 n - c_2 nlog log n.$$ |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |