Sandwiching a densest subgraph by consecutive cores

DOI10.1002/rsa.20543zbMath1322.05085OpenAlexW2056191455MaRDI QIDQ3192385

Pu Gao

Publication date: 12 October 2015

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

Full work available at URL: https://doi.org/10.1002/rsa.20543

zbMATH Keywords

\(k\)-coredensest subgraphbalanced \(k\)-core thresholddensest core

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Cites Work

• Encores on cores
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Sudden emergence of a giant \(k\)-core in a random graph
• On the threshold for \(k\)-regular subgraphs of random graphs
• Load balancing and orientability thresholds for random hypergraphs
• Almost all graphs with 1.44n edges are 3-colorable
• Performance of global load balancing by local adjustment
• Cores in random hypergraphs and Boolean formulas

This page was built for publication: Sandwiching a densest subgraph by consecutive cores