Size and connectivity of the k-core of a random graph

DOI10.1016/0012-365X(91)90162-UMaRDI QIDQ1179277zbMATH OpenDBLPWikidataFDO

Authors Tomasz Łuczak

Publication date 26 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90162-U

zbMATH Keywords

connectivityrandom graph

Mathematics Subject Classification ID

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

Review text

The \(k\)-core of a graph is the maximal subgraph with no degree below \(k\). Asymptotic estimates are given of the size and connectivity of the \(k\)- core of a Bernoulli graph.

Recommendations

• Sudden emergence of a giant k-core in a random graph
• Thek-Core and Branching Processes
• Asymptotic normality of the \(k\)-core in random graphs
• A simple solution to the k‐core problem

Cites work

• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4039956 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• The chromatic number of random graphs at the double-jump threshold

Cited in

(32)

• Phase transition phenomena in random discrete structures
• Sudden emergence of a giant k-core in a random graph
• Collapsibility and vanishing of top homology in random simplicial complexes
• Loose cores and cycles in random hypergraphs
• Core forging and local limit theorems for the \(k\)-core of random graphs
• Hamiltonicity in random graphs is born resilient
• On resilience of connectivity in the evolution of random graphs
• Degree sequences of monocore graphs
• A central limit theorem for diffusion in sparse random graphs
• Phase transition of degeneracy in minor-closed families
• Cores of random graphs are born Hamiltonian
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• The cook-book approach to the differential equation method
• Cores and shells of graphs.
• Dense peelable random uniform hypergraphs
• Hamiltonian cycles and subsets of discounted occupational measures
• Phase transitions in graphs on orientable surfaces
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
• Density decompositions of networks
• Conflict-free colouring of graphs
• Thek-Core and Branching Processes
• On the spread of random graphs
• The stripping process can be slow. II
• Almost all graphs with average degree 4 are 3-colorable
• The coreness and H-index of random geometric graphs
• On the rank, kernel, and core of sparse random graphs
• Peeling close to the orientability threshold. Spatial coupling in hashing-based data structures
• Component games on random graphs
• The k-core in percolated dense graph sequences
• On the robustness of random k-cores
• Asymptotic normality of the \(k\)-core in random graphs
• Finite size scaling for the core of large random hypergraphs

This page was built for publication: Size and connectivity of the \(k\)-core of a random graph

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