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)|
|Number of pages||9|
|Journal||Graphs and Combinatorics|
|State||Published - Dec 1987|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics