Size and connectivity of the \(k\)-core of a random graph. (English) Zbl 0752.05046

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.


05C80 Random graphs (graph-theoretic aspects)
05C40 Connectivity
Full Text: DOI


[1] Bollobás, B., Graphs theory — an introductory course, (1979), Springer Berlin · Zbl 0411.05032
[2] Bollobás, B., Random graphs, (1985), Academic Press New York · Zbl 0567.05042
[3] Bollobás, B., The evolution of sparse graphs, (), 35-57
[4] Bollobás, B.; Fenner, T.I.; Frieze, A.M., Long cycles in sparse random graphs, (), 59-64 · Zbl 0958.05122
[5] Erdős, P.; Rényi, A., On the evolution of random graphs, MTA mat. kut. int. Közl, 5, 17-61, (1960)
[6] Hoeffding, W., Probability inequalities for sums of bounded variables, J. amer. statist., 58, 13-30, (1963) · Zbl 0127.10602
[7] Łuczak, T., On matchings and Hamiltonian cycles in subgraphs of random graphs, (), 171-185
[8] Łuczak, T.; Wierman, J.C., The chromatic number of random graphs at the double-jump threshold, Combinatorica, 9, 39-49, (1989) · Zbl 0715.05056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.