2022/10/17 by Sahar Diskin, Diskin, Sahar, Dor Elboim +1
Computer Science · Mathematics · #05C80 #90C27 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2210.08900
openalex publication_date 2022/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G, we denote by f(G,u0,k) the number of paths of length k in G starting from u0. In graphs of maximum degree 3, with edge weights i.i.d. with exp(1), we provide a simple proof showing that (under the assumption that f(G,u0,k)=ω(1)) the expected weight of the heaviest path of length k in G starting from u0 is at least (1-o(1))(k+(log2(f(G,u0,k)))/(2)), and the expected weight of the lightest path of length k in G starting from u0 is at most (1+o(1))(k-(log2(f(G,u0,k)))/(2)). We demonstrate the immediate implication of this result for Hamilton paths and Hamilton cycles in random cubic graphs, where we show that typically there exist paths and cycles of such weight as well. Finally, we discuss the connection of this result to the question of a longest cycle in the giant component of supercritical G(n,p).