The first k-regular subgraph is large

DOI10.1017/S0963548314000169MaRDI QIDQ5418809zbMATH OpenFDO

Authors Pu Gao

Publication date 28 May 2014

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

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove that for sufficiently large k, there exist $0lesigm{a}_{k}leep{s}_{k}o0$ as $koinfty$, such that asymptotically almost surely the first k-regular subgraph appeared in the random graph process where one edge is added at a time has size between $(1-ep{s}_k)|K_k|$ and $(1-sigm{a}_k)|K_k|$, where $K_k$ denotes the $k$-core of the graph.

Recommendations

• \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph
• Regular subgraphs of random graphs
• On the threshold for k-regular subgraphs of random graphs
• The property of having a k-regular subgraph has a sharp threshold
• (k+1)-Cores Have k-Factors

Cites work

• (k+1)-Cores Have k-Factors
• Asymptotic enumeration by degree sequence of graphs of high degree
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• On the threshold for k-regular subgraphs of random graphs
• Regular subgraphs of random graphs
• Sudden emergence of a giant k-core in a random graph
• The property of having a k-regular subgraph has a sharp threshold

Cited in

(5)

• \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph
• Threshold functions for small subgraphs in simple graphs and multigraphs
• On the threshold for k-regular subgraphs of random graphs
• The property of having a k-regular subgraph has a sharp threshold
• Regular subgraphs of random graphs

This page was built for publication: The first \(k\)-regular subgraph is large

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