The Diameter of a Cycle Plus a Random Matching

DOI10.1137/0401033zbMath0664.05036OpenAlexW2151221105MaRDI QIDQ3815330

Béla Bollobás, Fan R. K. Chung

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401033

zbMATH Keywords

matchingdiameterexpandersrandom matchingRamanujan graphsn-cycle

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Related Items (32)

On the Diameter of Hyperbolic Random Graphs ⋮ On the Diameter of Hyperbolic Random Graphs ⋮ Some remarks on rainbow connectivity ⋮ On the average path length of a cycle plus random edges ⋮ Global dynamics of an epidemic model with incomplete recovery in a complex network ⋮ Smoothed Analysis on Connected Graphs ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Catastrophic event phenomena in communication networks: a survey ⋮ The clustering coefficient and the diameter of small-world networks ⋮ Local/Global Phenomena in Geometrically Generated Graphs ⋮ Diameters of random circulant graphs ⋮ Expander graphs and gaps between primes ⋮ A modified bootstrap percolation on a random graph coupled with a lattice ⋮ The Diameter of Sparse Random Graphs ⋮ Graphs with small diameter after edge deletion ⋮ The small world effect on the coalescing time of random walks ⋮ Greedy pathlengths and small world graphs ⋮ Navigation in small-world networks: a scale-free continuum model ⋮ Optimal routing in a small-world network ⋮ An explicit infinite family of \(\mathbb{M}\)-vertex graphs with maximum degree \(K\) and diameter \([1+o(1)\log_{K-1}\mathbb{M}\) for each \(K-1\) a prime power] ⋮ Pegging Graphs Yields a Small Diameter ⋮ THE MAGNETIC EDEN MODEL ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Mixing Time of Random Walk on Poisson Geometry Small World ⋮ ADVERTISING AND IRREVERSIBLE OPINION SPREADING IN COMPLEX SOCIAL NETWORKS ⋮ Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\) ⋮ Non-equilibrium opinion spreading on 2D small-world networks ⋮ Evolutionary dynamics on graphs -- the effect of graph structure and initial placement on mutant spread ⋮ The Mixing Time of the Newman-Watts Small-World Model ⋮ An analysis of the fixation probability of a mutant on special classes of non-directed graphs ⋮ Unnamed Item ⋮ Close to optimal decentralized routing in long-range contact networks

This page was built for publication: The Diameter of a Cycle Plus a Random Matching