The diameter of random regular graphs
COMBINATORICAPublished 1 June 1982
Béla Bollobás, W. Fernandez de la Véga
Citations169
SJR quartileQ1
SJR score1.27
SNIP1.58
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞) are given.
Abstract
We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).
Keywords
Mathematics
Discrete mathematics and its applicationsExtremal Graph Theory
1,684 Citations2013Béla Bollobás, Vladimir Nikiforov
European Journal of CombinatoricsA Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
1,192 Citations1980Béla Bollobás
The method determines the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and gives analogous formulae for hypergraphs.
Journal of Combinatorial Theory Series AThe asymptotic number of labeled graphs with given degree sequences
996 Citations1978Edward A. Bender, E. Rodney Canfield
Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: each row sum is specified and bounded, and a specified “sparse” set of entries must be zero.
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.
Canadian Journal of MathematicsDiameters of Random Graphs
42 Citations1981Victor Klee, David Larman
The present paper deals with the family G approximate (n,E) of all labeled graphs that have n nodes and E edges, which is a combinatorial foundation for investigations of the average-case behavior of various graph-theoretic algorithms.