Large induced degenerate subgraphs (Q1092059): Difference between revisions

A graph G is called d-degenerate (for a positive integer d), if every non-empty subgraph of G contains a vertex of degree smaller than d. The symbol \(\alpha_ d(G)\) denotes the maximum number of vertices of an induced d-degenerate subgraph of G. Further \(e_ d(n,m)\) is the minimum number of edges of a graph G with n vertices and with \(\alpha_ d(G)=m\). The main results are contained in two theorems. The first of them gives a formula for \(e_ 2(n,m)\), in the second a sharp lower bound for \(\alpha_ d(G)\) is expressed, depending on the degrees of vertices of G. Some concluding remarks are added.