THE MAXIMUM NUMBER OF HAMILTONIAN PATHS IN TOURNAMENTS

被引：25

作者：

ALON, N ^{[1
]}

机构：

[1] TEL AVIV UNIV,SCH MATH SCI,RAYMOND & BEVERLY SACKLER FAC EXACT SCI,IL-69978 TEL AVIV,ISRAEL

来源：

COMBINATORICA | 1990年 / 10卷 / 04期

关键词：

AMS subject classification (1980): 05C20; 05C35; 05C38;

D O I：

10.1007/BF02128667

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament on n vertices is at most c . n3/2 . n!/2n-1, where c is a positive constant independent of n.

引用

页码：319 / 324

页数：6

共 10 条

[1]

Bregman L. M, 1973, SOV MATH DOKL, V14, P945

[2]

BREGMAN LM, 1973, DOKL AKAD NAUK SSSR+, V221, P27

[3]

EGORYCHEV GP, 1981, DOKL AKAD NAUK SSSR+, V258, P1041

[4]

Erdos P., 1974, PROBABILISTIC METHOD

[5]

FALIKMAN DI, 1981, MATH ZAMETKI, V19, P931

[6]

Minc Henryk, 1963, B AM MATH SOC, V69, P789

[7]

Moon J. W., 1968, TOPICS TOURNAMENTS

[8] SHORT PROOF OF MINC CONJECTURE [J].

SCHRIJVER, A .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 25 (01) :80-83

[9]

SPENCER J, 1987, 10 LECTURES PROBABIL

[10]

Szele T., 1943, KIZEPISKOLAI MATEMAT, V50, P223

← 1 →