On the maximum number of Hamiltonian paths in tournaments

Ilan Adler; Noga Alon; Sheldon M. Ross

doi:10.1002/rsa.1010

On the maximum number of Hamiltonian paths in tournaments

Ilan Adler, Noga Alon, Sheldon M. Ross

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e - o(1))(n!/2^n-1).

Original language	English (US)
Pages (from-to)	291-296
Number of pages	6
Journal	Random Structures and Algorithms
Volume	18
Issue number	3
DOIs	https://doi.org/10.1002/rsa.1010
State	Published - May 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.1010

Cite this

@article{33218fc2820e4006bc73ebe0b1a47172,

title = "On the maximum number of Hamiltonian paths in tournaments",

abstract = "By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e - o(1))(n!/2n-1).",

author = "Ilan Adler and Noga Alon and Ross, {Sheldon M.}",

year = "2001",

month = may,

doi = "10.1002/rsa.1010",

language = "English (US)",

volume = "18",

pages = "291--296",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "3",

}

TY - JOUR

T1 - On the maximum number of Hamiltonian paths in tournaments

AU - Adler, Ilan

AU - Alon, Noga

AU - Ross, Sheldon M.

PY - 2001/5

Y1 - 2001/5

N2 - By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e - o(1))(n!/2n-1).

AB - By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e - o(1))(n!/2n-1).

UR - http://www.scopus.com/inward/record.url?scp=0035592248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035592248&partnerID=8YFLogxK

U2 - 10.1002/rsa.1010

DO - 10.1002/rsa.1010

M3 - Article

AN - SCOPUS:0035592248

SN - 1042-9832

VL - 18

SP - 291

EP - 296

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -

On the maximum number of Hamiltonian paths in tournaments

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this