The Diameter of a Cycle Plus a Random Matching

SIAM Journal on Discrete MathematicsPublished 1 August 1988

B Bollobás, Fan Chung

DOI10.1137/0401033

Source URL

Citations178

SJR quartileQ1

SJR score1.09

SNIP1.23

TL;DR

This paper shows that the graph consisting of an n-cycle and a random matching has diameter about $\log _2 n$, which is very close to the best possible value.

Abstract

Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 05 May 1987Accepted: 18 January 1988Published online: 08 August 2006Keywordsdiameter, random graphs, expandersAMS Subject Headings05CPublication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec

Keywords

Computer ScienceMathematics

Discrete mathematics and its applicationsExtremal Graph Theory

1,684 Citations2013Béla Bollobás, Vladimir Nikiforov

COMBINATORICAEigenvalues and expanders

1,170 Citations1986Noga Alon

It is shown that a regular bipartite graph is an expanderif and only if the second largest eigenvalue of its adjacency matrix is well separated from the first.

COMBINATORICARamanujan graphs

1,003 Citations1988Alexander Lubotzky, Ralph S. Phillips +1 more

The girth ofX is asymptotically ≧4/3 logk−1 ¦X¦ which gives larger girth than was previously known by explicit or non-explicit constructions.

SIAM Journal on Algebraic and Discrete MethodsExplicit Concentrators from Generalized <i>N</i>-Gons

251 Citations1984R. Michael Tanner

COMBINATORICAThe diameter of random regular graphs

169 Citations1982Béla Bollobás, W. Fernandez de la Véga

Asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞) are given.

Transactions of the American Mathematical SocietyThe diameter of random graphs

141 Citations1981Béla Bollobás

Almost every graph with n labelled vertices and m edges has diameter d and it is shown that if d = d(n) > 3 and m = m( n) satisfy (log n)/d - 3 log log n -> oo, 2rf_Imd'/'nd+x - log n -» oo and dd~2md~l/nd — log n – oo.

View PDF

SIAM Journal on ComputingSuperconcentrators

118 Citations1977Nicholas Pippenger

Journal of Graph TheoryDiameter bounds for altered graphs

85 Citations1984Fan Chung, M. R. Garey

This article provides bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D.

Cambridge University Press eBooksGRAPHS AND INTERCONNECTION NETWORKS: DIAMETER AND VULNERABILITY

74 Citations1983J Bermond, J. Bond +2 more

IEEE Transactions on ComputersDense Trivalent Graphs for Processor Interconnection

47 Citations1982Leland, Solomon

A new family of undirected graphs is presented that allows N processors to be connected in a network of diameter 3/2 log2 N + O(1), while only requiring that each processor be connected to three neighbors.

View PDF