The longest path in a random graph

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

doi:10.7282/t3-tvnn-ck74

Back

Journal article

Open access

Peer reviewed

The longest path in a random graph

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

Combinatorica, Vol.1, pp.1-12

1981

DOI:

https://doi.org/10.7282/t3-tvnn-ck74

Abstract

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

Files and links (3)

pdf

AKSz(1981)_The longest path In a random graph571.03 kBDownload View

Version of Record (VoR) Open Access

url

https://doi.org/10.1007/BF02579172View

Version of Record (VoR) Combinatorica

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

196 File downloads

118 Record Views

Details

Title: Subtitle: The longest path in a random graph
Creators: Miklós Ajtai (Author) - IBM Almaden
János Komlós (Author) - Mathematics, Rutgers University
Endre Szemerédi (Author) - Computer Science (New Brunswick), Rutgers University
Publication Details: Combinatorica, Vol.1, pp.1-12
Date published: 1981
Publisher: Rutgers University
Number of pages: 1 online resource (12 pages)
Academic Unit: School of Arts and Sciences; Computer Science (SAS); Mathematics (SAS)
Language: English
Resource Type: Journal article
Identifiers: 991031550002004646