Abstract
A graph H is d-degenerate if every subgraph of it contains a vertex of degree smaller than d. For a graph G, let αd(G) denote the maximum number of vertices of an induced d-degenerate subgraph of G. Sharp lowers bounds for αd(G) in terms of the degree sequence of G are obtained, and the minimum number of edges of a graph G with n vertices and α2(G) ≤ m is determined precisely for all m ≤ n.
Original language | English (US) |
---|---|
Pages (from-to) | 203-211 |
Number of pages | 9 |
Journal | Graphs and Combinatorics |
Volume | 3 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1987 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics