Sequences realizable by maximal k‐degenerate graphs
Mieczysław Borowiecki, Jaroslav Ivančo, Peter Mihók, Gabriel Semanišin · Journal of Graph Theory · 1995
Abstract A graph G is called k‐degenerate if every subgraph of G has a vertex of degree at most k. A k‐degenerate graph G is maximal k‐degenerate if for every edge e ϵ E(G), G + e is not k‐degenerate. Necessary and sufficient conditions for the sequence II = (d1, d2, ⃛, dp) to be a degree sequence of a maximal k‐degenerate graph G are presented. © 1995 John Wiley & Sons, Inc.