1990/09/01 by Graham Brightwell, Peter Winkler · 6 citations
Computer Science · Mathematics · #1-planar graph #Bound graph #Clique number #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph power #Hitting time #Line graph #Markov Chains and Monte Carlo Methods #Mathematics #Optimization and Search Problems #Path graph #Random graph #Random regular graph #Vertex (graph theory) #Wheel graph
paper · doi:10.1002/rsa.3240010303
openalex publication_date 1990/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/11
Abstract For x and y vertices of a connected graph G , let T G (x, y) denote the expected time before a random walk starting from x reaches y . We determine, for each n > 0, the n ‐vertex graph G and vertices x and y for which T G (x, y) is maximized. the extremal graph consists of a clique on ⌊(2 n + 1)/3⌋) (or ⌈)(2 n − 2)/3⌉) vertices, including x , to which a path on the remaining vertices, ending in y , has been attached; the expected time T G (x, y) to reach y from x in this graph is approximately 4 n 3 /27.