The longest path in a random graph

Miklós Ajtai; János Komlós; Endre Szemerédi

doi:10.1007/BF02579172

The longest path in a random graph

Miklós Ajtai, János Komlós, Endre Szemerédi

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

74 Scopus citations

Abstract

A random graph with (1+ε)n/2 edges contains a path of length cn. A random directed graph with (1+ε)n edges contains a directed path of length cn. This settles a conjecture of Erdõs.

Original language	English (US)
Pages (from-to)	1-12
Number of pages	12
Journal	Combinatorica
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF02579172
State	Published - Mar 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

AMS subject classification (1980): 05C38, 60C05, 60J80

Access to Document

10.1007/BF02579172

Cite this

@article{310c6a086cdb47e1aa25ffd3df4a3179,

title = "The longest path in a random graph",

abstract = "A random graph with (1+ε)n/2 edges contains a path of length cn. A random directed graph with (1+ε)n edges contains a directed path of length cn. This settles a conjecture of Erd{\~o}s.",

keywords = "AMS subject classification (1980): 05C38, 60C05, 60J80",

author = "Mikl{\'o}s Ajtai and J{\'a}nos Koml{\'o}s and Endre Szemer{\'e}di",

year = "1981",

month = mar,

doi = "10.1007/BF02579172",

language = "English (US)",

volume = "1",

pages = "1--12",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - The longest path in a random graph

AU - Ajtai, Miklós

AU - Komlós, János

AU - Szemerédi, Endre

PY - 1981/3

Y1 - 1981/3

N2 - A random graph with (1+ε)n/2 edges contains a path of length cn. A random directed graph with (1+ε)n edges contains a directed path of length cn. This settles a conjecture of Erdõs.

AB - A random graph with (1+ε)n/2 edges contains a path of length cn. A random directed graph with (1+ε)n edges contains a directed path of length cn. This settles a conjecture of Erdõs.

KW - AMS subject classification (1980): 05C38, 60C05, 60J80

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

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

U2 - 10.1007/BF02579172

DO - 10.1007/BF02579172

M3 - Article

AN - SCOPUS:51249183911

SN - 0209-9683

VL - 1

SP - 1

EP - 12

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

The longest path in a random graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this