# 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.

• This is not the same, but has a similar feel - if you repeatedly remove a vertex of minimum degree, and take the maximum value you encounter during this process, then you get a well-defined graph parameter called the degeneracy of the graph. Maybe this gives an example you might try to generalise. Aug 3, 2020 at 5:04
• Thanks @GordonRoyle. This is indeed of similar feel and could give a good start. I will look into this notion and think further on it. Aug 3, 2020 at 6:30
• Two somewhat related questions were posted here: mathoverflow.net/questions/378933/random-subgraph-properties and here: mathoverflow.net/questions/381631/… Jan 25, 2021 at 8:49