On the threshold for \(k\)-regular subgraphs of random graphs

DOI10.1007/s00493-011-2545-3zbMath1263.05099arXiv0706.1103OpenAlexW1966530078MaRDI QIDQ2428631

Paweł Prałat, Nicholas C. Wormald, Jacques Verstraete

Publication date: 26 April 2012

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

random graphthresholdregular subgraphs\(k\)-core\(k\)-factor\(k\)-factor-critical\(k\)-regular graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

(k+1)-Cores Have k-Factors, Sandwiching a densest subgraph by consecutive cores, Threshold functions for small subgraphs in simple graphs and multigraphs, Elimination schemes and lattices, \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph, The Firstk-Regular Subgraph is Large, Hamiltonicity in random graphs is born resilient, Cores of random graphs are born Hamiltonian

Cites Work

• Unnamed Item
• Encores on cores
• The first cycles in an evolving graph
• Sudden emergence of a giant \(k\)-core in a random graph
• The mixing time of the giant component of a random graph
• (k+1)-Cores Have k-Factors
• A simple solution to the k‐core problem
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• Cycles and Unicyclic Components in Random Graphs
• Regular subgraphs of random graphs
• Poisson Cloning Model for Random Graphs
• A Short Proof of the Factor Theorem for Finite Graphs