Smaller subgraphs of minimum degree k

MaRDI QIDQ2409841zbMATH OpenFDO

Authors Frank Mousset, Andreas Noever, Nemanja Škorić

Publication date 16 October 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.00273, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph theoryminimum degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35)

Abstract: In 1990 ErdH{o}s, Faudree, Rousseau and Schelp proved that for $kgeq2$, every graph with $ngeqk+1$ vertices and $$ edges contains a subgraph of minimum degree $k$ on at most $n-sqrtn/sqrt6k^3$ vertices. They conjectured that it is possible to remove at least $epsilo{n}_{k}n$ many vertices and remain with a subgraph of minimum degree $k$, for some $epsilo{n}_k>0$. We make progress towards their conjecture by showing that one can remove at least $Omega(n/logn)$ many vertices.

Review text

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.

Recommendations

• A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree k
• Subgraphs of minimal degree \(k\)
• scientific article; zbMATH DE number 3959468
• scientific article; zbMATH DE number 969094
• Sizes of graphs with induced subgraphs of large maximum degree

Cites work

• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• Subgraphs of minimal degree \(k\)

Cited in

(3)

• A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree k
• Minimum clique-free subgraphs of Kneser graphs
• Subgraphs of minimal degree \(k\)

This page was built for publication: Smaller subgraphs of minimum degree \(k\)

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