Random graphs with forbidden vertex degrees

DOI10.1002/RSA.20307MaRDI QIDQ3055889zbMATH OpenOpenAlexFDO

Authors G. R. Grimmett, Svante Janson

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.0270

zbMATH Keywords

even graphrandom graphrandom-cluster model

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the random graph G_{n,lambda/n} conditioned on the event that all vertex degrees lie in some given subset S of the non-negative integers. Subject to a certain hypothesis on S, the empirical distribution of the vertex degrees is asymptotically Poisson with some parameter mux given as the root of a certain `characteristic equation' of S that maximises a certain function psis(mu). Subject to a hypothesis on S, we obtain a partial description of the structure of such a random graph, including a condition for the existence (or not) of a giant component. The requisite hypothesis is in many cases benign, and applications are presented to a number of choices for the set S including the sets of (respectively) even and odd numbers. The random emph{even} graph is related to the random-cluster model on the complete graph K_n.

Recommendations

• A critical point for random graphs with a given degree sequence
• scientific article; zbMATH DE number 219310
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• scientific article; zbMATH DE number 747040
• A new approach to the giant component problem

Cites work

• A critical point for random graphs with a given degree sequence
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A simple solution to the k‐core problem
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Logarithmic combinatorial structures: A probabilistic approach
• Sudden emergence of a giant k-core in a random graph
• The asymptotic distribution of short cycles in random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The birth of the giant component
• The probability that a random multigraph is simple
• The Random-Cluster Model
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Thek-Core and Branching Processes

Cited in

(13)

• Weakly constrained-degree percolation on the hypercubic lattice
• Constrained-degree percolation in random environment
• The constrained-degree percolation model
• Shifting the phase transition threshold for random graphs using degree set constraints
• Focusing of maximum vertex degrees in random faulty scaled sector graphs
• On conditional internet graphs whose vertex degrees have no mathematical expectation
• A new approach to the giant component problem
• Random graphs with a fixed maximum degree
• Constrained-degree percolation on the hypercubic lattice: uniqueness and some of its consequences
• Exponential decay for constrained-degree percolation
• Constrained volume-difference site percolation model on the square lattice
• A general coupling for Ising models and beyond
• Automorphisms of random graphs with specified vertices

This page was built for publication: Random graphs with forbidden vertex degrees

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