3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 3, 2020 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – Jimmy
    Aug 3, 2020 at 6:30
  • $\begingroup$ Two somewhat related questions were posted here: mathoverflow.net/questions/378933/random-subgraph-properties and here: mathoverflow.net/questions/381631/… $\endgroup$ Jan 25, 2021 at 8:49

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.