Random regular graphs of high degree
From MaRDI portal
For a positive integer-valued function \(d= d(n)\) the model \(G_{n,d}\) of random regular graphs is defined to consist of all regular graphs on \(n\) vertices of degree \(d\) with uniform probability distribution. This paper provides a range of results on asymptotic properties of \(G_{n,d}\) as \(n\to\infty\) when \(d(n)\) grows more quickly than \(\sqrt n\). Its aim is to fill the gap in the range of possible values of \(d\) since, as the authors claim, ``at the present time nothing has really been published for \(d\) bigger than \(\sqrt n\). The properties of \(G_{n,d}\) studied in the paper include connectivity, Hamiltonicity, independent set size, chromatic number, choice number, and the size of the second eigenvalue, among others.
Recommendations
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Random regular graphs of non-constant degree: concentration of the chromatic number
- Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Extreme degrees in random subgraphs of regular graphs
Cites work
- A note on Hamiltonian circuits
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Almost all cubic graphs are Hamiltonian
- Almost all regular graphs are hamiltonian
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Automorphisms of random graphs with specified vertices
- Choosability in random hypergraphs
- Cliques in random graphs
- Coloring graphs with sparse neighborhoods
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- List coloring of random and pseudo-random graphs
- On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
- On the independence and chromatic numbers of random regular graphs
- On the independence number of random graphs
- The asymptotic connectivity of labelled regular graphs
- The Choice Number of Dense Random Graphs
- The chromatic number of random graphs
- The chromatic number of random graphs
- The eigenvalues of random symmetric matrices
- Uniform generation of random regular graphs of moderate degree
Cited in
(60)- On the chromatic number of random \(d\)-regular graphs
- Random regular graphs of non-constant degree: concentration of the chromatic number
- Counting sets with small sumset and applications
- Size biased couplings and the spectral gap for random regular graphs
- Sandwiching random graphs: universality between random graph models
- Sandwiching dense random regular graphs between binomial random graphs
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- The average distance and the diameter of dense random regular graphs
- Edge rigidity and universality of random regular graphs of intermediate degree
- Exchangeable pairs, switchings, and random regular graphs
- Voting rules that are unbiased but not transitive-symmetric
- Hamilton decompositions of regular expanders: applications
- Lower bounds on the chromatic number of random graphs
- On the structure of random graphs with constant r-balls
- Random Latin square graphs
- Discrepancy properties for random regular digraphs
- Regular induced subgraphs of a random graph
- Hamilton cycles in 3-out
- Local resilience and hamiltonicity maker-breaker games in random regular graphs
- Adjacency matrices of random digraphs: singularity and anti-concentration
- Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
- Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
- Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
- scientific article; zbMATH DE number 4099367 (Why is no real title available?)
- Concentration of non‐Lipschitz functions and applications
- Critical percolation on random regular graphs
- Perfect matchings and Hamiltonian cycles in the preferential attachment model
- On the asymmetry of random regular graphs and random graphs
- Sparse random graphs: eigenvalues and eigenvectors
- Expanders Are Universal for the Class of All Spanning Trees
- Dirac's theorem for random regular graphs
- Subgraph counts for dense random graphs with specified degrees
- Complete Minors in Graphs Without Sparse Cuts
- Anti-concentration property for random digraphs and invertibility of their adjacency matrices
- Almost all Steiner triple systems are almost resolvable
- Lower bounds for sense of direction in regular graphs
- Loose Hamilton Cycles in Regular Hypergraphs
- On the spread of random graphs
- Expanders are universal for the class of all spanning trees
- Reputation preferences resolve social dilemmas in spatial multigames
- Sandwiching biregular random graphs
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Hamiltonicity of graphs perturbed by a random regular graph
- Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
- Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
- On the second eigenvalue of random bipartite biregular graphs
- scientific article; zbMATH DE number 7731163 (Why is no real title available?)
- On random irregular subgraphs
- Hamiltonicity of randomly perturbed graphs
- Resilience with respect to Hamiltonicity in random graphs
- Hamilton cycles in pseudorandom graphs
- Embedding theorems for random graphs with specified degrees
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Hamilton cycles in pseudorandom graphs (extended abstract)
- On the maximum number of common neighbours in dense random regular graphs
- Sprinkling with random regular graphs
- Approximate Itai-Zehavi conjecture for random graphs
- Small subgraphs of random regular graphs
- On the chromatic number of random regular graphs
- Large sets in finite fields are sumsets
This page was built for publication: Random regular graphs of high degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746213)
