The longest path in a random graph

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

Type: Article

Publication Date: 1981-03-01

Citations: 138

DOI: https://doi.org/10.1007/bf02579172

View Publication

Locations

COMBINATORICA - View

Similar Works

Action	Title	Year	Authors
+	Long paths in sparse random graphs	1982	Béla Bollobás
+	The Median of the Number of Simple Paths on Three Vertices in the Random Graph	2020	Maksim Zhukovskii
+	The expected length of a shortest path	1993	Robert P. Davis Armand Prieditis
+	On the average path length of a cycle plus random edges	2015	Dimbinaina Ralaivaosaona Samah M. Osman Taha
+ PDF Chat	Longest Paths in Random Hypergraphs	2021	Oliver Cooley Frederik Garbe Eng Keat Hng Mihyun Kang Nicolás Sanhueza‐Matamala Julian Zalla
+	The Random Graph	2013	Peter J‎. Cameron
+	The size of the largest hole in a random graph	1993	Tomasz Łuczak
+	Optimal path in random networks with disorder: A mini review	2004	Shlomo Havlin Lidia A. Braunstein Sergey V. Buldyrev Reuven Cohen Tomer Kalisky Sameet Sreenivasan H. Eugene Stanley
+	The Optimal Path in an Erd˝ os-Renyi Random Graph	2004	Lidia A. Braunstein Sergey V. Buldyrev Sameet Sreenivasan Reuven Cohen Shlomo Havlin H. Eugene Stanley
+	Bounding the distance among longest paths in a connected graph	2017	Jan Ekstein Shinya Fujita Adam Kabela Jakub Teska
+	Exact solution for average path length in random graphs	2002	Agata Fronczak Piotr Fronczak Janusz A. Hołyst
+	Distances in random graphs	2007	Remco van der Hofstad
+	Longest paths in digraphs	1981	J.-C. Bermond A. Germa Marie-Claude Heydemann Dominique Sotteau
+	Length of optimal path in random networks with strong disorder	2003	Sergey V. Buldyrev Lidia A. Braunstein Reuven Cohen Shlomo Havlin H. Eugene Stanley
+	Restricted random walks on a graph	1999	F. Y. Wu H. Russell Kunz
+	Intersection of Longest Paths in a Graph	2011	Susanna F. de Rezende Cristina G. Fernandes Daniel M. Martin Yoshiko Wakabayashi
+	Optimal path and cycle decompositions of random graphs	2016	Daniela Kühn
+ PDF Chat	Isolated trees in a random graph	1982	Zbigniew Pałka
+	Random Graphs, a Whirlwind Tour of	2011	Fan Chung
+ PDF Chat	A Sequential Algorithm for Generating Random Graphs	2009	Mohsen Bayati Jeong Han Kim Amin Saberi

Works That Cite This (119)

Action	Title	Year	Authors
+ PDF Chat	Large cycles in random generalized Johnson graphs	2021	В. С. Кожевников А. М. Райгородский Maksim Zhukovskii
+ PDF Chat	Expansion in supercritical random subgraphs of the hypercube and its consequences	2022	Joshua Erde Mihyun Kang Michael Krivelevich
+	Introduction	1985	Maurice Pouzet
+ PDF Chat	Turán‐type problems for long cycles in random and pseudo‐random graphs	2023	Michael Krivelevich Gal Kronenberg Adva Mond
+	Long paths in sparse random graphs	1982	Béla Bollobás
+ PDF Chat	An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph	2013	Graeme Kemkes Nicholas Wormald
+ PDF Chat	Cycle Factors and Renewal Theory	2015	Jeff Kahn Eyal Lubetzky Nicholas Wormald
+ PDF Chat	Long paths and Hamiltonicity in random graphs	2016	Michael Krivelevich
+	An analogue of the Erd\H{o}s-Gallai theorem for random graphs	2019	József Balogh Andrzej Dudek Lina Li
+ PDF Chat	Longest Paths in Random Hypergraphs	2021	Oliver Cooley Frederik Garbe Eng Keat Hng Mihyun Kang Nicolás Sanhueza‐Matamala Julian Zalla

Works Cited by This (0)

Action	Title	Year	Authors