The Diameter of a Cycle Plus a Random Matching

DOI10.1137/0401033MaRDI QIDQ3815330zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Fan 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)

Recommendations

• Decreasing the diameter of cycles
• The diameter of a random graph with bounded diameter
• Diameters of random circulant graphs
• The diameter of sparse random graphs
• The diameter of randomly perturbed digraphs and some applications

Cited in

(32)

• The mixing time of the Newman-Watts small world
• The clustering coefficient and the diameter of small-world networks
• Smoothed Analysis on Connected Graphs
• Diameters of random circulant graphs
• The small world effect on the coalescing time of random walks
• Greedy pathlengths and small world graphs
• Optimal routing in a small-world network
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• A modified bootstrap percolation on a random graph coupled with a lattice
• The Mixing Time of the Newman-Watts Small-World Model
• The diameter of sparse random graphs
• Global dynamics of an epidemic model with incomplete recovery in a complex network
• An analysis of the fixation probability of a mutant on special classes of non-directed graphs
• On the diameter of hyperbolic random graphs
• On the diameter of hyperbolic random graphs
• Local/Global Phenomena in Geometrically Generated Graphs
• On the average path length of a cycle plus random edges
• Expander graphs and gaps between primes
• 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
• Graphs with small diameter after edge deletion
• Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\)
• Catastrophic event phenomena in communication networks: a survey
• Mixing Time of Random Walk on Poisson Geometry Small World
• Evolutionary dynamics on graphs -- the effect of graph structure and initial placement on mutant spread
• Random walks on edge coloured random graphs
• Improved (In-)Approximability Bounds for d-Scattered Set
• Pegging graphs yields a small diameter
• ADVERTISING AND IRREVERSIBLE OPINION SPREADING IN COMPLEX SOCIAL NETWORKS
• Navigation in small-world networks: a scale-free continuum model
• Non-equilibrium opinion spreading on 2D small-world networks
• THE MAGNETIC EDEN MODEL
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815330)