The maximum degree of a random graph

DOI10.1017/S0963548300004491MaRDI QIDQ2711619zbMATH OpenOpenAlexFDO

Authors Oliver Riordan, Alex Selby

Publication date 30 October 2001

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300004491

zbMATH Keywords

approximationdistribution functionsnormal densityrandom graphrandom variables

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Review text

Let \(G\) be a random graph from the standard model \(G(n,p)\). Thus \(G\) has \(n\) vertices in which each possible edge appears independently with probability \(p\) (\(0< p< 1\), \(q= 1-p\)). Let \(\phi\) and \(\Phi\) denote the standard normal density and distribution functions, respectively. The main result of this paper is as follows:NEWLINENEWLINENEWLINEFor a random graph \(G\) from \(G^*(n,p)\), let \(p_n= P[\max d(G)\leq np +b\sqrt{npq}]\), where \(b\) is fixed. Then we have \(p^{{1\over n}}_n\to c\) as \(n\to\infty\); where \(c\) is a constant independent of \(p\) and depending only on \(b\) and is given by \(c= \max_\theta[\Phi(b+ \theta)\text{Exp}(-{\theta^2\over 2})]\). The above maximum is attained (uniquely) at \(\theta_0= \theta_0(b)\), the root of the equation \(\theta_0\Phi(b+ \theta_0)= \phi(b+\theta)\). For \(p={1\over 2}\) and \(b=0\), we have \(\theta_0= 0.506\dots\) and \(c= 0.6102\dots\)\ .NEWLINENEWLINENEWLINEThe proof presented here is based on considering the complete graph \(K_n\) with weights on the edges, and taking these weights as independent normal \(N(p,pq)\) random variables giving a continuous approximation to \(G^*(n,p)\).

Recommendations

• Random graphs with a fixed maximum degree
• The maximum degree of random planar graphs
• The maximum degree of random planar graphs
• On the Maximum Degree of a Random Planar Graph
• Extreme degrees in random graphs
• On the size of a random maximal graph
• scientific article; zbMATH DE number 3847442
• The maximum and minimum degrees of random bipartite multigraphs
• On the number of vertices of given degree in a random graph

Cited in

(20)

• On the distribution of the maximum k-degrees of the binomial random graph
• Synchronization in networks with strongly delayed couplings
• Optimizing Gershgorin for symmetric matrices
• The distribution of the maximum number of common neighbors in the random graph
• Asymptotic distribution of modularity in networks
• The maximal degree in a Poisson-Delaunay graph
• Concentration of maximum degree in random planar graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• scientific article; zbMATH DE number 4179410 (Why is no real title available?)
• On the number of vertices of given degree in a random graph
• scientific article; zbMATH DE number 4155658 (Why is no real title available?)
• A Gumbel distribution approach of extremes in the degree sequence
• Some remarks about extreme degrees in a random graph
• Extreme degrees in random graphs
• The Maximum Block Size of Critical Random Graphs
• A bound on normal approximation of number of vertices of a fixed degree in a random graph
• The maximum and minimum degrees of random bipartite multigraphs
• On perfectly friendly bisections of random graphs
• Quantum glassiness from efficient learning
• The irredundance number and maximum degree of a graph

This page was built for publication: The maximum degree of a random graph

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