Degree sequences after vertex removals Consider a graph $G=(V, E)$ with $|V|=n$ vertices. Let $(v_1, \dots, v_n)$ be an ordered list of its vertices. Let $G_i=G[\{v_{i+1}, \dots, v_n\}]$ be the induced subgraph on the last $n-i$ vertices. Let $(d_1, \dots, d_n)$ be the degree sequence of $G_i$: $d_i$ is the degree of $v_i$ in $G_i$.
I wonder whether such sequences have been studied, as they raise  natural and interesting questions.
For instance, my original motivation is to obtain, for a given graph, such a sequence that is maximum with respect to the majorization order. A natural strategy would be to choose $v_1$ with maximum degree in $G_0$, $v_2$ with maximum degree in $G_1$, and so on. But there is an ambiguity when several vertices have the maximum degree, and other sequences may make sense.
Thank you for any information and suggestions.
 A: Several works study the degree sequence obtained when vertices are removed from random graphs with given degree sequence. Vertices are generally removed by decreasing order of degrees, or uniformly at random, but other variants are considered. Some empirical works also consider various kinds of real-world complex networks (like, e.g., the internet, web graphs, or biological networks).
The general goal of these works is to estimate the robustness of graphs to failures (random removals) and attacks (targeted removals), through the size of the largest connected component of the remaining graph. In the random setting, this is strongly related to the remaining degree sequence. And in all cases, it is shown that targeted attacks and failures have similar effects on purely random graph (ER model), whereas degree sequences met in practice make graphs much more sensitive to attack than to failures, and than purely random graphs.
Notice that this is strongly related epidemiology: vertex removals may be seen as vaccination campaigns, and the question of which individuals to vaccinate first certainly is the hottest topic these days.
I co-authored in 2009 a quite comprehensive survey of these works, but surely much progress has been made since then. This may be a good entry point, though, as we put some efforts in trying to shed light on the underlying assumptions and formal approaches, when available.
