
doi: 10.1007/bf01788542
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.
Extremal problems in graph theory, d-degenerate graph, vertex degree
Extremal problems in graph theory, d-degenerate graph, vertex degree
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 36 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
