THE MAXIMUM NUMBER OF HAMILTONIAN PATHS IN TOURNAMENTS

被引：22

作者：

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
SCHRIJVER, A
[J]. 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 →