Smaller subgraphs of minimum degree \(k\) (Q2409841)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Smaller subgraphs of minimum degree \(k\) |
scientific article |
Statements
Smaller subgraphs of minimum degree \(k\) (English)
0 references
16 October 2017
0 references
Summary: In [Discrete Math. 85, No. 1, 53--58 (1990; Zbl 0714.05033)], \textit{P. Erdős} et al. proved that for \(k \geq 2\), every graph with \(n \geq k+1\) vertices and \((k-1)(n-k+2)+\binom{k-2}{2}+1\) edges contains a subgraph of minimum degree \(k\) on at most \(n-\sqrt{n/6k^3}\) vertices. They conjectured that it is possible to remove at least \(\varepsilon_k n\) many vertices and remain with a subgraph of minimum degree \(k\), for some \(\varepsilon_k0\). We make progress towards their conjecture by showing that one can remove at least order of \(\Omega(n/\log n)\) many vertices.
0 references
graph theory
0 references
minimum degree
0 references