Swap Equilibria under Link and Vertex Destruction

Abstract

We initiate the study of the destruction or adversary model (Kliemann 2010) using the swap equilibrium (SE) stability concept (Alon et al., 2010). The destruction model is a network formation game incorporating the robustness of a network under a more or less targeted attack. In addition to bringing in the SE concept, we extend the model from an attack on the edges to an attack on the vertices of the network. We prove structural results and linear upper bounds or super-linear lower bounds on the social cost of SE under different attack scenarios. For the case that the vertex to be destroyed is chosen uniformly at random from the set of max-sep vertices (i.e., where each causes a maximum number of separated player pairs), we show that there is no tree SE with only one max-sep vertex. We conjecture that there is no tree SE at all. On the other hand, we show that for the uniform measure, all SE are trees (unless two-connected). This opens a new research direction asking where the transition from “no cycle” to “at least one cycle” occurs when gradually concentrating the measure on the max-sep vertices.

1. Introduction

Game theoretic models for the study of the decentralized formation of networks have gained remarkable attention during the past two decades. In most of those models, the vertices of a graph correspond to players, and each player’s choice of action can have an influence on the structure of the graph. Models vary according to the different actions available to the players and regarding the criteria under which the quality of the graphs are evaluated. For the latter, most models have focused on centrality-type criteria, for example players aim to minimize the sum of distances over all other players. Recently, robustness aspects have been addressed in the form of the destruction model (also known as the adversary model) [1,2,3,4]. In this model, players anticipate the destruction of exactly one edge in the graph, and the cost function for each player v gives the expected number of other players that v will no longer be able to reach after the destruction. Social cost is the sum of all players’ costs, which is equal to the expected number of separated vertex pairs, that is the expected number of all ordered pairs $(v,w)$ such that there is no path anymore between v and w after the destruction has taken place. The model allows many variations, since the edge to be destroyed is determined randomly according to a probability measure that may even depend on the graph (this dependence is known to the players)1.

In this work, we use the stability concept of swap equilibrium (SE) [5] for the destruction model. Moreover, we extend the model to the destruction of exactly one vertex instead of an edge. We will henceforth speak of the edge destruction model and the vertex destruction model in order to distinguish the two.

Previous and Related Work

Network formation games date back to the 1990s; see Jackson and Wolinsky [6] for an early publication. In computer science, network formation games have gained attention since the work by Fabrikant et al. [7] in 2003. The destruction model was introduced by Kliemann in 2010 [1] and subsequently studied in a series of publications [2,3,4]. The focus was on the price of anarchy for Nash equilibrium (NE) and pairwise stability (PS). We give a comparison between the NE and PS results for the destruction model with the results on SE in this work in Section 2.1. Earlier works on robustness in network formation include [6,8,9,10,11]. None of those earlier models allows a structure-dependent destruction probability as in the destruction model; for a detailed discussion, we refer to ([2] Section 4).

The stability concepts of NE and PS require an edge cost parameter $\alpha \in {\mathbb{R}}_{>0}$. Computationally deciding whether a graph constitutes an NE is hindered by an exponential search space and can indeed be NP-hard [7]. This has raised concerns about the applicability of the model since we should not expect players to solve an NP-hard problem. Therefore, many variations have been introduced in order to make the model more tractable. Usually, the idea is to limit the choices of the players, for example to single-edge deviations [6,12]. An even more drastic approach was suggested by Alon et al. in 2010 [5]. They removed the α parameter and considered only edge swaps: a graph is a swap equilibrium if no player can improve his or her cost by removing an incident edge and then creating a new incident edge; this action is called an edge swap. It is also allowed to simply remove an incident edge without creating a new one, which usually makes sense if edges can be harmful, e.g., if cost incorporates the risk of contagion. A variation introduced by Mihalák and Schlegel in 2012 [13] is the inclusion of edge ownerships: each edge is owned by exactly one of its endpoints and may only be swapped (or removed) by its owner. The resulting stability concept is called asymmetric swap equilibrium (ASE). We will not consider edge ownerships or ASE in this work, but this extension is most certainly interesting for future work.

The following three recent publications address robustness in a network formation framework similar to ours:

• Meirom et al. [14] consider a cost function that uses a linear combination of the lengths of two short disjoint paths. The idea is that the players build a graph where, for each shortest path, there is a backup path of reasonable length.
• Goyal et al. [15] consider a model where each player, in addition to building edges, can choose to immunize themselves in exchange for a fee. Then, an adversary selects a connected component of non-immunized vertices to destroy; an alternative description is that the adversary picks a vertex, and then, the destruction spreads from there, while immunized vertices act as firewalls. A player’s utility is the expected size of his or her connected component after the destruction has taken place, which is zero if the player herself/himself is destroyed. This utility is almost exactly the positive version of our cost: if $\mathcal{C}(v)$ is the expected number of cut-off vertices, then $n-\mathcal{C}(v)$ is the expected size of v’s component after the attack (we differ in that if the player herself/himself is attacked, we say that she/he is cut off from $n-1$ vertices, so her/his component size is one, not zero). However, the kind of destruction is very different from ours. Although it can be formulated as an attack on a vertex, the contagious properties of the attack move the focus to different connectivity properties of the attacked vertex in comparison to our model. For example, if a leaf (that is, a vertex of degree one) is attacked in our model, the overall damage is relatively small: namely, we have $2(n-1)$ separated vertex pairs. In their model, however, if the neighbor of the leaf is not immunized, the destruction will spread, and the overall damage can be much higher. For earlier work on network formation with contagious risk, see [16].
• Chauhan et al. [17] extended the edge destruction model by incorporating distances: the cost for player v is the expected sum of distances to all other players after edge destruction.

In another line of research [18,19,20,21], the robustness of networks is studied in a two-player game. The first player is the designer and can choose which edges to form in the network, while the second player is the adversary or disruptor, who can destroy vertices or edges in the network. Some of those models allow immunization of vertices or edges. All of those models are very different from ours since the network is formed by a central authority, the designer, and not in a decentralized manner as in our model. Moreover, the adversaries in those models work differently from ours: they typically act more deterministically and not randomized as our adversaries (or they randomize in simpler ways than ours), but on the other hand, they are more powerful, since they can destroy more than one edge or one vertex.

If, for our type of adversary, we had a network designer, then that designer would simply build an optimal network. Optimal networks for the case that we have link costs α and edge destruction have been identified as cycle and star, independent of the adversary and only depending on the range of α [2,4]. Therefore, the designer’s job would be simple: look at α, and then, decide whether to build a cycle or a star. If there are no link costs, as in the SE model, the notion of optimality is not straightforward in the first place. However, given a fixed number of edges k, we can define optimal graphs as those with minimal cost among all graphs with k edges. If $k\ge n$, then any graph with a cycle traversing all of the vertices is optimal in this sense, for edge and for vertex destruction independent of the actual destroyer. If $k=n-1$, then for any edge destroyer, the star is optimal (optimality for vertex destruction is not straightforward for $k=n-1$).

2. Results

We prove quantitative and structural results for two types of destroyers under the stability concept of swap equilibrium (SE): the uniform destroyer picks an edge or vertex uniformly at random, while the extreme destroyer picks an edge or vertex uniformly at random from the set of edges or vertices, respectively, where the destruction of each causes a maximum number of vertex pairs to be separated. An edge or vertex that does the latter is called a max-sep edge or max-sep vertex, respectively. In addition, we consider some variations. For edge destruction, the most notable variation is a destroyer that chooses an edge from the set of bridges uniformly at random. For vertex destruction, we consider that the probability for destruction of a vertex v is proportional to its degree $deg(v)$, which we call the degree-proportional destroyer.

We prove that for uniform and extreme edge destruction and uniform bridge destruction, an SE is bridgeless or has a star-like structure. A consequence of this is that in terms of social cost, those SE are very efficient, namely the social cost of any of those SE is $𝒪$(n). For uniform vertex destruction, we prove that if an SE is not two-connected, then it is a tree. This again implies an $𝒪$(n) bound on the social cost.

For the degree-proportional vertex destroyer, the situation is very different. Social cost of an SE can be as high as $\Omega (n^2)$, which is the highest order possible in this model. This lower bound is attained on a simple graph, namely a star.

For extreme vertex destruction, we also give a super-linear lower bound on the social cost of SE, namely $\Omega (n^{3/2})$. The construction is still roughly star-like, but more complicated: we need a clique of certain size at the center unto which paths of a certain length are attached.

Finally, we prove a structural result for extreme vertex destruction: if $n\ge 8$, there is no tree SE with only one max-sep vertex. This means that in a tree SE (with $n\ge 8$), the extreme destroyer will always have at least two vertices to choose from.

2.1. Discussion of Results and Comparison with Previous Work

What kind of (decentralized) network formation is most effective against a destroyer? This question cannot be fully answered yet. However, we can make the following observations.

Consider first that we face the uniform edge destroyer. All three models, namely Nash equilibrium (NE), pairwise stability (PS) and swap equilibrium (SE), provide relatively robust networks. For NE and PS, this has been shown in previous work [2,4] by proving a price of anarchy of $𝒪$(1), meaning that the cost of an equilibrium network is at most a constant factor away from that of an optimal network. For SE, we prove here that the social cost of an equilibrium is upper-bounded by $2(n-1)$, which means that the destroyer can cut off at most one vertex from the rest of the graph (resulting in $2(n-1)$ separated vertex pairs). This equates to relatively small damage. It is only beaten by a graph with a cycle that traverses all vertices, which has zero social cost. Note that non-equilibrium graphs can have super-linear social cost, e.g., the path has social cost $\Omega (n^2)$, following from the computation in ([2], Proposition 8.1).

In [17], the uniform edge destroyer is combined with a different cost function, which is the expected sum of distances to other players after destruction (instead of considering the number of cut-off vertices). NE is used as the equilibrium concept. A bound of $𝒪$($1+\alpha /\sqrt{n}$) is proven on the price of anarchy, which is a good bound. Note in particular that it is constant for $\alpha \le \sqrt{n}$.

Now, consider that we face the extreme edge destroyer. One of the most striking previous results is that for NE, the price of anarchy is still $𝒪$(1) ([2], Theorem 9.8). For PS, the situation flips, and the worst possible order is obtained for the price of anarchy ([4], Theorem 4), if $\alpha =\Omega (1)$. The lower-bound example used in the proof exploits the two properties of PS: we only consider single-edge deviations, and the agreement of both endpoints is required to build an edge. For SE, we prove here that the destroyer can cut off at most one vertex from the rest of the graph, just like for the uniform destroyer. Therefore, although NE and SE differ computationally (exponential versus quadratic search space), they both provide relatively robust networks when faced with the extreme edge destroyer.

For vertex destruction, NE and PS have not been studied previously, so we cannot make a comparison with those. The results that we prove here for SE resemble those for edge destruction and PS: relatively robust networks for the uniform destroyer and less robust ones for the extreme destroyer (linear social cost versus super-linear social cost). It should be emphasized that the degree-proportional destroyer, which arguably takes a simpler approach than the extreme destroyer, can have SE even with quadratic cost, which is the worst possible order. An explanation is that this destroyer combines the unpredictability of the uniform destroyer, on the one hand, with the focus on destruction expressed by the extreme destroyer, on the other hand (higher-degree vertices tend to cause more damage when destroyed). Indeed, the proof for the quadratic lower bound relies crucially on the way in which this destroyer randomizes.

A comparison between edge destruction and vertex destruction can be done only for SE currently. Removing an edge can leave us with at most two connected components. Removing a vertex v can leave us with $deg(v)$ connected components (not counting v itself; cf. the exact definition in Section 3). This suggests that the model is theoretically harder to handle and that the destroyer can do more damage in terms of separated vertex pairs. However, for the uniform destroyer, the fundamental proof ideas turn out to be roughly similar (namely opening a cycle to capture more vertices and bounding the diameter of a tree SE), although technically much more involved for vertex destruction.

For the extreme destroyer, edge and vertex destruction are clearly more divergent from each other than for the uniform destroyer. This is reflected by our results: for edge destruction, we have a linear bound on the social cost of SE, while for vertex destruction, we have a super-linear lower bound and no upper bound at this time. The lower-bound example clearly does not work for extreme edge destruction, as explained in Remark 2. The difficulty with extreme vertex destruction is that already swapping a single leaf can have profound effects on the destroyer’s probability measure. That is, if a leaf a swaps its one edge $ab$ for an edge $ac$, then the number of components when c is destroyed increases. This can lead to c becoming the only max-sep vertex in the new graph. This signifies a drastic change, provided that before the swap, there were many max-sep vertices in different parts of the graph. It should be noted that we have no lemma saying that max-sep vertices are distributed in a certain pattern in the graph, whereas for edge destruction, it is known that they form a star-like structure ([2], Proposition 9.1).

2.2. Open Problems

We have extensive experimental evidence and indications on the theory side that our structural result for the extreme vertex destroyer (that there is no SE tree with only one max-sep vertex for $n\ge 8$) can be extended in two ways. We conjecture for $n=\Omega (1)$:

(i)

There is no SE graph under extreme vertex destruction with only one max-sep vertex (this extends our result for trees to general graphs).

(ii)

There is no SE graph under extreme vertex destruction that is a tree (this extends our non-existence result for trees with one max-sep vertex to trees in general).

Recall that we prove that unless the graph is two-connected, an SE cannot contain cycles for the uniform vertex destroyer. On the other hand, for the extreme vertex destroyer, our Conjecture (ii) would imply that an SE is only possible if we have at least one cycle. It would then be interesting to find a family ${{\mathcal{D}}^{\epsilon }}_{\epsilon \in [0,1]}$ of vertex destroyers, such that ${\mathcal{D}}^0$ is the uniform destroyer and ${\mathcal{D}}^1$ is the extreme destroyer, and the others are something suitable in between. When moving ε from zero to one, the probability measure should concentrate more and more on the max-sep vertices. It would be interesting to find out at which values of ε the situation switches from no non-two-connected SE having a cycle to each SE having a cycle. Our Conjecture (ii) would imply that it must switch an odd number of times.

Other interesting directions include:

• Closing the gap between our lower $\Omega (n^{3/2})$ bound and the trivial $𝒪$($n^2$) upper bound for social cost of extreme vertex destruction.
• Extension to edge ownerships and the asymmetric swap equilibrium.
• Study of the model from [17] under swap equilibrium or asymmetric swap equilibrium.
• Study of vertex destruction under Nash equilibrium or pairwise stability as the equilibrium concept.

3. Model and Notation

Fix the number of players $n\in {\mathbb{N}}_{\ge 3}$. All our graphs are finite, simple and undirected. The undirected edge $\{v,w\}$ between vertices v and w is denoted $vw$ or $wv$. Denote ${\mathcal{G}}_n$ the set of all graphs on the vertex set $V_n:=[n]:=\{1,\dots ,n\}$. We use the term player and vertex synonymously for graphs in ${\mathcal{G}}_n$. A swap for a graph $G\in {\mathcal{G}}_n$ is a triple of players $(a,b,c)$, such that $ab\in E(G)$ and $ac\notin E(G)$. Denote $S(G)\subseteq V_n^3$ the set of all swaps of G. Denote $G+(a,b,c)$ the graph that is obtained from G by removing $ab$ and inserting $ac$; we say that player a swaps her/his edge $ab$ for the new edge $ac$. A cost function ${\mathcal{C}}_G$ for $G\in {\mathcal{G}}_n$ assigns to each player $v\in V_n$ a number ${\mathcal{C}}_G(v)\in {\mathbb{R}}_{\ge 0}$. The social cost of G is $SC(G):={\sum }_{v\in V_n}{\mathcal{C}}_G(v)$. We call G a swap equilibrium (SE) if ${\mathcal{C}}_G(a)\le {\mathcal{C}}_{G+(a,b,c)}(a)$ for all $(a,b,c)\in S(G)$ and ${\mathcal{C}}_G(a)\le {\mathcal{C}}_{G-ab}(a)$ for all $ab\in E(G)$.

Edge destruction: Let $G\in {\mathcal{G}}_n$ be connected. For $v,w\in V_n$, denote ${\mathcal{R}}_G(v,w)$ the set of all v-w paths in G. The relevance of $e\in E(G)$ for $v\in V_n$ is:

$${rel}_G(e,v):=|\{w\in V_n;\forall P\in \mathcal{R}(v,w):e\in E(P)\}|.$$

That is, the number of those vertices where for each of them holds: in order to reach it from v, we necessarily have to traverse edge e. When e is removed from the graph, then there will be exactly ${rel}_G(e,v)$ vertices that v will no longer be able to reach; we also say that those vertices are cut off from v or that v is cut off from them. An edge destroyer $\mathcal{D}$ is a map that associates with each $G\in {\mathcal{G}}_n$ a probability measure ${\mathcal{D}}_G$ on $E(G)$, that is ${\mathcal{D}}_G(e)\in [0,1]$ for each e, and ${\sum }_{e\in E(G)}{\mathcal{D}}_G(e)=1$. Given $\mathcal{D}$, we define the cost for player v in G as:

$${\mathcal{C}}_G(v):=\sum _{e\in E}{rel}_G(e,v){\mathcal{D}}_G(e),$$

that is, the expected number of vertices from which v will be cut off after one edge is removed randomly according to the measure ${\mathcal{D}}_G$. If G is disconnected, cost is defined to be ∞.

The separation $sep(e)$ of an edge $e\in E(G)$ is the number of ordered player pairs $(v,w)$ such that the removal of e will destroy all v-w paths in G. If e is a non-bridge, then clearly $sep(e)=0$. Otherwise, $G-e$ has exactly two components, say $K_1,K_2\subseteq V_n$, and we call $\nu (v):=min\{|K_1|,|K_2|\}$ the minimal-component size of e. Then, $sep(e)=2\nu (e)(n-\nu (e))$. It is easy to see that $SC(G)={\sum }_{e\in E(G)}sep(e){\mathcal{D}}_G(e)$.

Vertex destruction: For the vertex destruction model, the destroyer $\mathcal{D}$ associates each $G\in {\mathcal{G}}_n$ with a probability measure on the vertices of G, that is ${\mathcal{D}}_G(v)\in [0,1]$ for each $v\in V_n$, and ${\sum }_{v\in V_n}{\mathcal{D}}_G(v)=1$. We define the destruction of a vertex not as its removal from the graph, but as the removal of all of its incident edges. This is reflected by the following definition of relevance and cost. The relevance of $u\in V_n$ for $v\in V_n$ is:

$${rel}_G(u,v):=|\{w\in V_n;\forall P\in \mathcal{R}(v,w):u\in V(P)\}|.$$

Note that since v is in every v-w path, we have ${rel}_G(v,v)=n-1$, which is exactly the number of vertices that will be cut off from v if all edges incident with v are removed. Given a vertex destroyer $\mathcal{D}$, we define the cost for player v in G as:

$${\mathcal{C}}_G(v):=\sum _{u\in V}{rel}_G(u,v){\mathcal{D}}_G(u).$$

Again, a disconnected graph induces infinite cost for each player.

The separation $sep(u)$ of a vertex $u\in V_n$ is the number of ordered player pairs $(v,w)$ such that the removal of u will destroy all v-w paths in G. It is again easy to see that $SC(G)={\sum }_{u\in V_n}sep(u){\mathcal{D}}_G(u)$. Moreover, if removal of u creates k components (not counting u itself) of sizes ${\beta }_1,\dots ,{\beta }_k$, we have:

$$sep(u)=n^2-1-\sum _{i=1}^k{\beta }_i^2.$$

(1)

When the graph G is clear from context, we omit the G subscripts or arguments. When a graph $G^{\prime }$ is defined, we write ${\mathcal{C}}^{\prime }$, ${rel}^{\prime }$, ${SC}^{\prime }$, etc., instead of ${\mathcal{C}}_{G^{\prime }}$, ${rel}_{G^{\prime }}$, $SC(G^{\prime })$, etc., respectively. The same goes for $G^{″}$.

For any connected graph $G=(V,E)$, we call $I\subseteq V$ an island if it is inclusion-maximal under the condition that the induced subgraph $G[I]$ is bridge-free (it does not matter whether we mean bridges of G or bridges of $G[I]$). The bridge tree $\tilde{G}$ of G is obtained by collapsing each island I of G to a single vertex $\tilde{I}$ and inserting an edge between $\tilde{I}$ and $\tilde{J}$ if and only if an edge runs in G between a vertex of I and a vertex of J. Obviously, $IJ\mapsto \tilde{I}\tilde{J}$ is a bijection between the set of bridges of G and the set of bridges of $\tilde{G}$, and we will often identify those two sets. We refer to [2] for a more formal treatment of the bridge tree.

We will also use the better-known block-cut-vertex tree; see, e.g., the book by Diestel [22] for a definition.

4. Uniform Edge and Uniform Bridge Destruction

Denote $B(G)\subseteq E(G)$ the set of all of the bridges of $G\in {\mathcal{G}}_n$ and:

$$S^B(G):=\{(a,b,c)\in S(G);ab\in B(G)\wedge G+(a,b,c)\mathrm{is}\mathrm{connected}\}$$

the set of bridge swaps (the case that $G+(a,b,c)$ is disconnected is not interesting since such a swap can never bring an improvement). Clearly, $ac\in B(G+(a,b,c))$ for each $(a,b,c)\in S^B(G)$.

An edge destroyer $\mathcal{D}$ is called the uniform edge destroyer if ${\mathcal{D}}_G(e)=\frac{1}{|E(G)|}$ for each $e\in E(G)$ and each $G\in {\mathcal{G}}_n$. It is called the uniform bridge destroyer if ${\mathcal{D}}_G(e)=\frac{1}{|B(G)|}$ for each $e\in B(G)$ and ${\mathcal{D}}_G(e)=0$ for each $e\in E(G)\setminus B(G)$, for each $G\in {\mathcal{G}}_n$ (if $B(G)=\varnothing$, the graph is two-edge-connected, and we can take any probability measure for ${\mathcal{D}}_G$ since the cost for each player is zero in any case).

In order to point out what are some of the essential properties of those destroyers, we look at more general destroyers first. Consider the following condition on a destroyer:

$$\begin{array}{cc}& \forall G\in {\mathcal{G}}_n\forall s=(a,b,c)\in S^B(G):\hfill \\ & \phantom{\wedge }{sep}_G(ab)={sep}_{G+s}(ac)\Rightarrow {\mathcal{D}}_G(ab)={\mathcal{D}}_{G+s}(ac)\hfill \\ & \wedge \forall e\in E(G)\cap E(G+s):{sep}_G(e)={sep}_{G+s}(e)\Rightarrow {\mathcal{D}}_G(e)={\mathcal{D}}_{G+s}(e)\hfill \end{array}$$

(2)

This means that if after a bridge swap an edge maintains its separation, then it also maintains its probability. This clearly includes the uniform edge destroyer and the uniform bridge destroyer. The next proposition shows that (2) is equivalent to the following simpler condition:

$$\begin{array}{cc}& \forall G\in {\mathcal{G}}_n\forall s=(a,b,c)\in S^B(G):\hfill \\ & \phantom{\wedge }{\mathcal{D}}_G(ab)={\mathcal{D}}_{G+s}(ac)\hfill \\ & \wedge \forall e\in E(G)\cap E(G+s):{\mathcal{D}}_G(e)={\mathcal{D}}_{G+s}(e)\hfill \end{array}$$

(3)

This means that each edge carries its fixed probability that, in the case of a bridge, sticks to it even when it is swapped for another edge.

Proposition 1.

(2) and (3) are equivalent.

Proof. 

It is clear that (3) implies (2). Therefore, let $\mathcal{D}$ be a destroyer with property (2). Let $G\in {\mathcal{G}}_n$ and $s=(a,b,c)\in S^B(G)$. Since ${\nu }_G(ab)={\nu }_{G+s}(ac)$, we have ${sep}_G(ab)={sep}_{G+s}(ac)$; hence, ${\mathcal{D}}_G(ab)={\mathcal{D}}_{G+s}(ac)$. Now, consider the special case first that $(a,b,c)$ is a path in the bridge tree. Then, the only separation that changes due to s is that of $bc$. Since separations of all other edges are maintained, they also maintain their probabilities. Since all of the probabilities add up to one, the edge $bc$ also maintains its probability. In the general case, we have a path $(v_0=b,v_1,\dots ,v_k=c)$. Conducting the sequence of swaps $(a,v_0,v_1),(a,v_1,v_2),\dots ,(a,v_{k-1},v_k)$ gives the graph $G+s$, and in each step, the edges maintain their probability. ☐

The following proof uses the basic idea from ([5], Theorem 1).

Lemma 1.

Let $\mathcal{D}$ be a destroyer with property (3). Then, the bridge tree of an SE with respect to $\mathcal{D}$ has a diameter at most two.

Proof. 

Let G be an SE, and for contradiction, assume that $(a,b,c,d)$ is a path in its bridge tree. Denote $n_a,n_b,n_c,n_d$ the number of vertices in the subtrees rooted at $a,b,c$ and d, respectively; hence, $n=n_a+n_b+n_c+n_d$. Consider the swap $s=(a,b,c)$. By (3), we have ${\mathcal{D}}_G(ab)={\mathcal{D}}_{G+s}(ac)$, and all of the other edges maintain their probabilities, as well. We have ${rel}_G(ab,a)={rel}_{G+s}(ac,a)$, and for all of the other edges, from the view of a, the only relevance that changes is that of $bc$, namely from $n_c+n_d$ to $n_b$. Since G is an SE, this means $n_c+n_d\le n_b$. Likewise, we consider the swap $(d,c,b)$ and obtain $n_a+n_b\le n_c$. Together, this implies $n_a\le 0$, which is impossible. ☐

Theorem 1.

Let G be an SE for the uniform edge destroyer. Then, G is bridgeless or a star; hence, $SC(G)\le 2(n-1)=𝒪(n)$.

Proof. 

If G is bridgeless, then $SC(G)=0$. Therefore, assume that G contains a bridge. We want to show that G is a tree, so for contradiction, assume that G is not a tree. Let I be an island containing a cycle, and let $bc$ be a bridge with $b\in I$ (and $c\in I^{\prime }$ for some island $I^{\prime }$). Then, there is a cycle C in I that traverses b. Choose a so that $ab\in E(C)$. Then, the swap $(a,b,c)$ puts the bridge $bc$ on a cycle and makes it part of the island, so its relevance for a drops from a positive value to zero. No new bridges are introduced, and the relevance of all other edges remains the same for player a. Hence, this is an improving swap, a contradiction to SE. The situation is depicted in Figure 1.

Since we know that G is a tree, G coincides with its bridge tree. By Lemma 1, $diam(G)\le 2$. Since $n\ge 3$, we conclude that G is a star. It follows that $SC(G)=2(n-1)$. ☐

Theorem 2.

Let G be an SE for the uniform bridge destroyer. Then, G is bridgeless or $\tilde{G}$ is a star, where each of the outer islands has exactly one vertex2. Hence, $SC(G)\le 2(n-1)=𝒪(n)$.

Proof. 

If G is bridgeless, then $SC(G)=0$. Therefore, assume that G contains a bridge. By Lemma 1, $\tilde{G}$ is a star. Let I be an island that is not the center of the star (i.e., it is an outer island) and that contains more than one vertex. Then, I contains a cycle. By a swap as in the proof of Theorem 1, the one bridge e between the center of the star and I can be put on a cycle. For the players in I, this is a strict improvement since for them, e had the strictly highest relevance of all bridges in G. The statement on the social cost follows since only one vertex can be separated from the rest of the graph by the removal of a bridge. ☐

5. Extreme Edge Destruction

For $G\in {\mathcal{G}}_n$, denote ${sep}_{\max }(G):={\max }_{e\in E(G)}sep(e)$ and:

$$E_{\max }(G):=\{e\in E(G);sep(e)={sep}_{\max }(G)\}.$$

We call the edges in $E_{\max }(G)$ the max-sep edges. Recall $sep(e)=2\nu (e)(n-\nu (e))$ and note that $x\mapsto x(n-x)$ is strictly increasing on $[0,n/2]$; hence, $\nu (e)=\nu (e^{\prime })$ for all $e,e^{\prime }\in E_{\max }(G)$. Moreover, if $\nu (e)=\nu (e^{\prime })$ for some $e\in E_{\max }(G)$ and $e^{\prime }\in E(G)$, then $e^{\prime }\in E_{\max }(G)$. In other words: exactly all of the edges with maximum $\nu (e)$ are max-sep.

An edge destroyer $\mathcal{D}$ is called the extreme edge destroyer if ${\mathcal{D}}_G(e)=\frac{1}{|E_{\max }(G)|}$ for each $e\in E_{\max }(G)$ and ${\mathcal{D}}_G(e)=0$ for each $e\in E(G)\setminus E_{\max }(G)$.

Theorem 3.

Let G be an SE under the extreme edge destroyer. Then, G is bridgeless or $\tilde{G}$ is a star, where each of the outer islands has exactly one vertex. Hence, $SC(G)\le 2(n-1)=𝒪(n)$.

Proof. 

The expression for the social cost follows from the structural statement. Assume for contradiction that G contains bridges and is not of the stated form.

Case 1: $E_{\max }=\{e_1,\dots ,e_k\}$ with $k\ge 2$. This situation is depicted in Figure 2. By ([2] Proposition 9.1), the max-sep edges form a star in the bridge tree. For each $i\in [k]$, denote $K_i\subseteq V_n$ the (unique) minimal component of $G-e_i$, and denote $K_0$ the island at the center of the star formed by $E_{\max }$. Then, $V_n={⊍}_{i=0}^k{K}_i$ and $|K_i|=|K_j|$ for all $i,j\in [k]$. By assumption, $|K_i|\ge 2$ for each i.

Case 1.1: There is a leaf $a\in K_1$. Denote b the neighbor of a, and let $v\in K_0$. Define $G^{\prime }:=G+(a,b,v)$. When moving from G to $G^{\prime }$, all of the edges $e_2,\dots ,e_k$, and the edges in $G[K_2],\dots ,G[K_k]$ have their separation maintained. Edges in $G[K_1]$ have their separation maintained or reduced since their minimal-component size reduces. The edge $e_1$ has its separation reduced since its minimal-component size reduces. The new edge $av$ cannot become max-sep since $\nu (av)=1$ while $\nu (e_2)\ge 2$. It follows that $E_{\max }^{\prime }=\{e_2,\dots ,e_k\}$. We have ${rel}^{\prime }(e_i,a)=rel(e_i,a)<rel(e_1,a)$ for all $i\ge 2$. Hence, ${\mathcal{C}}^{\prime }(a)<\mathcal{C}(a)$, a contradiction to SE.

Case 1.2: There is a cycle C in $K_1$. Let $ab\in E(C)$ and $v\in K_0$. By essentially the same arguments as in Case 1.1, we show that player a improves by the swap $(a,b,v)$.

Case 2: $E_{\max }=\{e_1\}$. This case is more difficult since after reducing the separation of $e_1$, we have no other max-sep edges that could act as a reference. Denote $K_1$ a component of $G-e_1$ with minimum size (if both components of $G-e_1$ have the same size, then pick one arbitrarily), and denote $K_0$ the island containing the endpoint of $e_1$ that is not in $K_1$.

Case 2.1: There is a leaf $a\in K_1$. Denote b the neighbor of a, and let $v\in K_0$. Define $G^{\prime }:=G+(a,b,v)$. We have ${\nu }^{\prime }(e_1)=\nu (e_1)-1$, so ${sep}^{\prime }(e_1)$ has the next lower possible value below $sep(e_1)$. Hence, $E_{\max }^{\prime }=\{e_1,e_2,\dots ,e_k\}$ for zero or more additional edges $e_2,\dots ,e_k$. Since they all have the same minimum-component size, they cannot be in $G[K_1]$; hence, they form a star with $K_0$ as the center (this is the only way that they can form a star in the bridge tree). If $av\notin E_{\max }^{\prime }$, then ${\mathcal{C}}^{\prime }(a)=\nu (e_1)-1<n-\nu (e_1)=\mathcal{C}(a)$; hence, the swap is an improvement. If $av\in E_{\max }^{\prime }$, then $\nu (e_1)-1={\nu }^{\prime }(av)=1$; so $|K_1|=2$ and $n\ge 4$. Moreover, $k\ge 2$. It follows that ${\mathcal{C}}^{\prime }(a)=\frac{1}{k}(n-1+(k-1)(\nu (e_1)-1))=\frac{n-2}{k}+1$. On the other hand, $\mathcal{C}(a)=n-2$. If $n\ge 5$ or $k\ge 3$, this implies an improvement. The remaining case of $n=4$ and $k=2$ is impossible, since for such n, the graph $G^{\prime }$ is a star, and thus, $k=3$.

Case 2.2: There is a cycle C in $K_1$. We consider a swap like the one in Case 1.2. It is not difficult to see that ${rel}^{\prime }(e,a)<rel(e_1,a)$ for each $e\in E_{\max }^{\prime }$; hence, the swap is an improvement. ☐

6. Uniform and Degree-Proportional Vertex Destruction

A vertex destroyer $\mathcal{D}$ is called the uniform vertex destroyer if ${\mathcal{D}}_G(u)=\frac{1}{n}$ for each $u\in V_n$ and each $G\in {\mathcal{G}}_n$.

For any connected graph $G=(V,E)$, denote $\mathcal{B}(G)$ the set of its blocks and $A(G)\subseteq V$ the set of its cut-vertices (also known as articulation points). Denote $\widehat{G}$ the block-cut-vertex tree of G, that is $V(\widehat{G})=\mathcal{B}(G)⊍A(G)$, and each edge in $\widehat{G}$ runs between a block and a cut-vertex, namely $Bv\in E(\widehat{G})$ if $B\in \mathcal{B}(G)$ and $v\in B\cap A(G)$. We have $|B|\ge 2$ for each $B\in \mathcal{B}(G)$. If $|B|\ge 3$, then $G[B]$ is two-connected; we also say that B is two-connected in G. Recall also that in a two-connected graph, for each vertex v, we can find a cycle that visits v.

The following remark is proven by standard arguments, which are included here for completeness.

Remark 1.

Let $G=(V,E)$ be any two-connected graph.

(i) 

Let $x,y,v\in V$ be three distinct vertices. Then, there exist paths $P=(v,\dots ,x)$ and $Q=(v,\dots ,y)$ with $V(P)\cap V(Q)=\{v\}$.

(ii) 

Let $W\subseteq V$ with $|W|\ge 2$ and $v\in V\setminus W$. Then, there are $x,y\in W$ with $x\ne y$ and paths $P=(v,\dots ,x)$ and $Q=(v,\dots ,y)$ with $V(P)\cap V(Q)=\{v\}$ and $V(P)\cap W=\{x\}$ and $V(Q)\cap W=\{y\}$.

Proof. 

(i) Add a new vertex z to the graph, and connect it with x and with y. The resulting graph is again two-connected. Using the global version of Menger’s theorem (see, e.g., ([22] Theorem 3.3.6)), we find two independent (that is, internally vertex-disjoint) v-z paths. Taking subpaths yields the result.

(ii) Let $x^{\prime },y^{\prime }\in W$, $x^{\prime }\ne y^{\prime }$ be any two distinct vertices in W. By (i), we find $P^{\prime }=(v,\dots ,x^{\prime })$ and $Q^{\prime }=(v,\dots ,y^{\prime })$ with:

$$V(P^{\prime })\cap V(Q^{\prime })=\{v\}.$$

(4)

Let x be the first vertex on $P^{\prime }$ that is also in W. Define $P:=(v,\dots ,x)$ as a subpath of $P^{\prime }$. Likewise, let y be the first vertex on $Q^{\prime }$ that is also in W, and define $Q:=(v,\dots ,y)$ as a subpath of $Q^{\prime }$. By (4), we get $x\ne y$, and the other properties follow from the choice of x and y. ☐

Definition 1.

Let $G=(V,E)$ be any graph and $(B_1,b_1,\dots ,B_k,b_k,B_{k+1})$, $k\ge 1$, be a path in its block-cut-vertex tree $\widehat{G}$. Assume $|B_1|\ge 3$, and let $C=(b_1,a,\dots ,b_1)$ be a cycle in $B_1$. Let $c\in B_{k+1}\setminus \{b_k\}$. Then, we call the swap $(a,b_1,c)$ a cycle extension with respect to $(B_1,B_{k+1})$; note that $B_2,\dots ,B_k$ and $b_1,\dots ,b_k$ are uniquely determined by the pair $(B_1,B_{k+1})$ since $\widehat{G}$ is a tree.

The name “cycle extension” is chosen since the cycle C is extended into a larger cycle, thereby merging the blocks that are traversed by the new cycle. The merging property is proven in the next proposition.

Proposition 2.

With notation as in Definition 1, denote $G^{\prime }:=G+(a,b_1,c)$. Then, in $G^{\prime }$, all of the blocks $B_1,\dots ,B_{k+1}$ are merged into one block, and the remaining blocks are maintained; in particular, no new cut-vertices emerge in $G^{\prime }$, and the separation values of maintained cut-vertices do not increase.

Proof. 

The only non-obvious part is that $B^{\prime }:=B_1\cup \dots \cup B_{k+1}$ is two-connected in $G^{\prime }$, which we will prove now. Denote $C=(b_1,a,a_1,\dots ,a_t,b_1)$ for some t. There is a cycle of the form $C^{\prime }=(b_1,\dots ,b_k,\dots ,c,a,a_1,\dots ,a_t,u_1)$ that starts in $B_1$, runs through $B_2,\dots ,B_{k+1}$ and finally re/enters $B_1$.

Let $i\in [k+1]$ with $|B_i|\ge 3$ and $v\in B_i\setminus V(C^{\prime })$. Claim: in $G^{\prime }$, there are paths $P=(v,\dots ,x)$ and $Q=(v,\dots ,y)$ with $x,y\in V(C^{\prime })$ and $x\ne y$, such that $V(P)\cap V(Q)=\{v\}$ and $V(P)\cap V(C^{\prime })=\{x\}$ and $V(Q)\cap V(C^{\prime })=\{y\}$.

Proof of claim: Denote $W:=V(C^{\prime })\cap B_i$, then $|W|\ge 2$. By Remark 1(ii) applied with W as defined here, the claim is clear for $i\ge 2$, since such $B_i$ is two-connected in $G^{\prime }$ (and in G). Hence, we consider $i=1$. The difficulty is that $B_1$ may not be two-connected in $G^{\prime }$, since we removed the edge $a_1{u}_1$. However, none of the paths P or Q guaranteed to exist by Remark 1(ii) in G can use $a_1{u}_1$ since then, that path would have more than one vertex in common with W. This concludes the proof of the claim.

Now, let $v,w\in B^{\prime }$ with $v\ne w$. We show that in $G^{\prime }$, there are two independent v-w paths.

• If $v,w\in B_i$ for some $i\le k$, then either $B_i$ is two-connected and the statement is clear, or $|B_i|=2$ in which case $v,w\in V(C^{\prime })$, and the independent paths are given through $C^{\prime }$.
• Let $v\in B_i$ and $w\in B_j$ for $i\ne j$. If v or w is located on $C^{\prime }$, then nothing has to be done for that vertex; otherwise, we connect it with $C^{\prime }$ via the paths guaranteed by the claim. It is easy to see that this gives two independent v-w paths.
• Let $v,w\in B_1$. In G, we find two independent v-w paths P and Q in $B_1$. At most, one of them, say P, uses $a{b}_1$. Instead of using that edge, we can, starting at $b_1$, run along $C^{\prime }$ until we reach a. That $b_1$-a path runs outside of $B_1$ (except for a and $b_1$) and, thus, will not interfere with P or Q. ☐

Theorem 4.

An SE for the uniform vertex destroyer is two-connected (that is, it has only one block) or it does not contain any cycle and, thus, is a tree.

Proof. 

Let an SE graph $G\in {\mathcal{G}}_n$ be given, and assume it contains more than one block. We only need to prove that no block has a cycle, or, equivalently, that each block consists of only two vertices. Suppose for contradiction that $B_1$ is a block with $|B_1|\ge 3$, and let $B_2$ be another block. Let $(a,b,c)$ be a cycle extension with respect to $(B_1,B_2)$ and $G^{\prime }:=G+(a,b,c)$. By Proposition 2, it follows that ${rel}^{\prime }(b,a)<rel(b,a)$, since in $G^{\prime }$, removal of b cannot cut a off the one or more vertices in $B_2\setminus \{b_1\}$ anymore (recall that a block always contains at least two vertices). All other relevance for a is maintained or also reduced. Therefore, we have an improvement in the cost of player a, contradicting the stability of G. ☐

Corollary 1.

Let $G\in {\mathcal{G}}_n$ be an SE for the uniform vertex destroyer. Then, G is either two-connected or a star; hence, $SC(G)=2(n-1)=𝒪(n)$ or $SC(G)=3n-5+\frac{2}{n}=𝒪(n)$.

Proof. 

Let G be non-two-connected. Then, by Theorem 4, G is a tree. By applying the same argument as in the proof of Lemma 1, we obtain that the diameter of G is at most two, i.e., G is a star. The social cost of star is easily computed to be $\frac{1}{n}\left((n-1)(3n-4)+2(n-1)\right)=3n-5+\frac{2}{n}$. ☐

A destroyer $\mathcal{D}$ is called the degree-proportional vertex destroyer if ${\mathcal{D}}_G(u)=\frac{{deg}_G(u)}{2m}$ for each $u\in V_n$ and each $G\in {\mathcal{G}}_n$.

Proposition 3.

The star is an SE for the degree-proportional vertex destroyer, and its social cost is $\frac{1}{2}(n^2+n)-1=\Omega (n^2)$.

Proof. 

Let $S\in {\mathcal{G}}_n$ be a star. First, we prove that S is an SE. Clearly, by just removing an edge (without creating a new one), no player can improve. It is also obvious that the only possibility for swapping is from one leaf to another leaf. Let $a,c\in V$ be leaves and b the center of the star. Denote $S^{\prime }:=S+(a,b,c)$. Although player a, by the swap $(a,b,c)$, decreases the number of cut-off vertices in the case that the center b is destroyed, this does not improve her/his cost. This is because at the same time, the degree of c is increased, and destruction of c in $G^{\prime }$ will cut off a from all other vertices. The following calculations show that a indeed does not improve her/his cost by the swap. We have:

$$\begin{array}{cc}\hfill {\mathcal{C}}_S(a)& =\frac{1}{2(n-1)}\sum _{w\in V}rel(w,a)·deg(w)=\frac{1}{2(n-1)}\left((n-1)+(n-2)+(n-1)(n-1)\right)\hfill \\ & =\frac{1}{2}\left(n+1-\frac{1}{n-1}\right)\hfill \end{array}$$

After swapping:

$$\begin{array}{c}\hfill {\mathcal{C}}_{S^{\prime }}(a)=\frac{1}{2(n-1)}\left(3(n-1)+{(n-2)}^2+(n-3)\right)=\frac{1}{2}\left(n+1-\frac{1}{n-1}\right)\end{array}$$

Hence, ${\mathcal{C}}_S(a)=C_{S^{\prime }}(a)$. Therefore, the star is an SE (an example for $n=6$ is given in Figure 3). Its social cost is:

$$\begin{array}{cc}\hfill SC(S)& =\frac{1}{2(n-1)}\sum _{v\in V}\sum _{w\in V}rel(w,v)·deg(w)\hfill \\ & =(n-1)\left(\frac{1}{2}\left(n+1-\frac{1}{n-1}\right)\right)+\frac{1}{2(n-1)}·(n-1)n\hfill \\ & =\frac{1}{2}\left((n^2-1)-1\right)+\frac{n}{2}=\frac{1}{2}{n}^2+n-1\hfill \end{array}$$

☐

Corollary 2.

The social cost of SE for the degree-proportional vertex destroyer can be as high as $\Omega (n^2)$, which is the worst possible order in the destruction model.

7. Extreme Vertex Destruction

This model is defined similarly to the extreme edge destruction model. Denote $V_{\max }$ the set of max-sep vertices and $n_{\max }:=|V_{\max }|$. The extreme vertex destroyer picks the vertex to destroy uniformly at random from $V_{\max }$.

We start with a first step toward understanding the worst-case order of social cost of an SE in this model, by giving an SE example with super-linear social cost, namely $\Omega (n^{3/2})$. The construction is shown in Figure 4. It is unknown at this time whether there is a matching upper bound. Before reading the proof of the following theorem, the reader is encouraged to take look at Remark 3 in order to obtain an idea why we have to limit the length of the paths attached to the clique.

Theorem 5.

Let $t\ge 4$ and $0\le k\le 4t-5=\Theta (t)$. Let $G=(V,E)$ be the graph consisting of a clique C on t vertices, and to each vertex of C, there is a path of length k attached (so, $n:=|V|=t(k+1)$). Then, G is an SE with $SC(G)=\Omega (n^{3/2})$.

Proof. 

For each player v at distance $0\le i\le k$ from C, we have:

$$sep(v)=2\left((n-1)+(k-i)(n-1-(k-i))\right)$$

Since $k-i\le (n-1)/2$ and since the function $x\mapsto x(n-1-x)$ is strictly increasing on $[0,(n-1)/2]$, separation is strictly largest when $i=0$, that is when $v\in C$. It follows $V_{\max }=C$ and:

$$\begin{array}{cc}\hfill SC(G)& =2(n-1)+k(n-1-k)=2\left(t(k+1)-1+k(t(k+1)-1-k)\right)\hfill \\ & =2tk+t-1+k^{2}t+kt-k-k^2\ge 2\left((2t-1)k+k^2(t-1)\right)\ge 2k^2(t-1)\ge k^{2}t\hfill \end{array}$$

If we choose k maximal, that is $k=4t-5$, we get:

$$SC(G)\ge k^{2}t={(4t-5)}^{2}t=(16t^2-40t+25)t\ge (6t^2+t(10t-40))t\ge 6t^3$$

Now, for this k, we have $n=t(k+1)=t(4t-4)\le 4t^2$; hence, $n^{3/2}\le 8t^3$. It follows $SC(G)\ge \frac{6}{8}{n}^{3/2}=\frac{3}{4}{n}^{3/2}=\Omega (n^{3/2})$ (in short: we have $SC(G)=\Omega (t{k}^2)$; if we choose k maximal, then $k=\Theta (t)$; hence, $SC(G)=\Omega (t^3)=\Omega (n^{3/2})$).

We prove the SE property. Just removing an edge (without building a new one) is clearly not an option for the players on the paths. For a player of the clique C, nothing changes when removing an edge, since because of $t\ge 4$, the set C remains two-connected.

For $u\in C$, denote $V_u$ the k vertices on the path attached to u (note that $u\notin V_u$). In the following, whenever we consider a swap, by $G^{\prime }$, we refer to the graph we obtain from G by applying the swap.

We start with the different swaps available to a player $a\in C$. We have $rel(u,a)=k+1$ for each $u\in V_{\max }\setminus \{a\}$; hence:

$$\mathcal{C}(a)=\frac{(n-1)+(t-1)(k+1)}{t}.$$

(i)

Consider a swap $(a,b,c)$ with $b\in C\cap N(a)$ and $c\in V_u$ for $u\in C\setminus \{a\}$, that is player a swaps an edge from the clique to some path, but not the one connected to a itself. Since $t\ge 4$, the set C remains two-connected. Separation of u and of some vertices in $V_u$ is reduced. All other separations are maintained. It follows:

$$\mathcal{C}(a)-{\mathcal{C}}^{\prime }(a)=\frac{(n-1)+(t-1)(k+1)}{t}-\frac{(n-1)+(t-2)(k+1)}{t-1}=\frac{k-n+2}{t(t-1)}<0$$

Hence, the swap is no improvement for player a.

(ii)

Consider a swap $(a,b,c)$ with $b\in C\cap N(a)$ and $c\in V_a$, that is player a swaps an edge from the clique to its own path. Again, since $t\ge 4$, the set C remains two-connected. The separation values on some vertices in $V_a$ decrease, but that does not change the set of max-sep vertices, nor their relevance for a. Hence, player a’s cost is maintained.

(iii)

Consider a swap $(a,b,c)$ with $b\in V_a$; then, in order to keep the graph connected, we have $c\in V_a$. That is, player a swaps the first edge on its path to some vertex on that path. We only have to exclude that c becomes max-sep; if we achieve that, then, we know that a’s cost is maintained. Let $2\le l\le k-1$ be the distance between a and c. Then, by (1):

$$\begin{array}{cc}& {sep}^{\prime }(c)<{sep}_{\max }\hfill \\ \hfill \iff & n^2-1-{(l-1)}^2-{(k-l)}^2-{(n-k)}^2<n^2-1-k^2-{(n-1-k)}^2\hfill \\ \hfill \iff & k^2+{(n-1-k)}^2<{(l-1)}^2+{(k-l)}^2+{(n-k)}^2\hfill \\ \hfill \iff & {(n-1-k)}^2<-2l(k+1-l)+1+{(n-k)}^2\hfill \\ \hfill \iff & -2(n-k)<-2l(k+1-l)\hfill \\ \hfill \iff & n-k>l(k+1-l)\Leftarrow n-k>\frac{{(k+1)}^2}{4}\hfill \\ \hfill \iff & t(k+1)>\frac{{(k+1)}^2}{4}+k\iff t>\frac{k+1}{4}+1-\frac{1}{k+1}\hfill \\ & 4t-5\ge k\hfill \end{array}$$

The latter is true by the restriction on k in the statement of the theorem. In this computation, we used again that the function $x\mapsto x(k+1-x)$ is increasing on $[0,(k+1)/2]$.

We continue with the swaps available to a player $a\in V_u$ for some $u\in C$.

(iv)

Consider a swap $(a,b,c)$ with $dist(u,a)<dist(u,b)$. Then, $c\in V_u$ with $dist(u,b)<dist(u,c)$; since otherwise, the graph would become disconnected. From a computation like in (iii), it follows that this swap cannot make c max-sep. Hence, the cost of player a does not change.

(v)

Consider a swap $(a,b,c)$ with $dist(u,a)>dist(u,b)$. If $c\in V_u$, then again, a’s cost will not change. If $c\in C$, then c will become the only max-sep vertex in the new graph, clearly increasing a’s cost.

Now, let $c\in V_w$ for some $w\ne u$, that is some vertices migrate from u’s path to w’s path. Separation of w and separation of the vertices $v\in V_w$ with $dist(w,v)\le dist(w,c)$ will increase. All other separations are reduced or maintained, so we have $V_{\max }^{\prime }\subseteq V_w\cup \{w\}$. In the best case, k vertices migrate to w’s path; only w becomes max-sep, and ${rel}^{\prime }(w,a)=n-2k$. In this case:

$$\begin{array}{cc}\hfill \mathcal{C}(a)-{\mathcal{C}}^{\prime }(a)& =\frac{(t-1)(k+1)+(n-k)}{t}-(n-2k)\hfill \\ & =\frac{(t-1)(k+1)+(t(k+1)-k)-t(t(k+1)-2k)}{t}\hfill \\ & =\frac{(k+1)(2t-t^2-1)+(2t-1)k}{t}\hfill \\ & \le (k+1)(2-t)+2k\le -2(k+1)+2k<0\hfill \end{array}$$

Hence, the swap is no improvement for player a. ☐

Remark 2.

The graph in Theorem 5 is no SE for extreme edge destruction.

Proof. 

The max-sep edges are the edges on the paths that have one endpoint in the clique. This will not change when a leaf swaps to the clique; hence, this leaf will experience an improvement. ☐

Remark 3.

The graph in Theorem 5 is no SE if $k\ge 4t-4=4(t-1)$, that is if k is larger than the upper bound in the theorem.

Proof. 

Let $a\in C$ and b be her/his neighbor in $V_a$. Let $c\in C$ be at distance l from a, to be specified later. Denote $G^{\prime }:=G+(a,b,c)$. If c becomes max-sep in $G^{\prime }$, then player a’s cost will decrease, since ${rel}^{\prime }(c,a)=k$, whereas the relevance of a max-sep vertex in G for a is $k+1$ or $n-1$. By the computation in Theorem 5(iii), we see that c becomes max-sep if $n-k\le l(k+1-l)$. We have:

$$n-k\le l(k+1-l)\iff t\le \frac{l(k+1-l)}{k+1}+1-\frac{1}{k+1}\Leftarrow t\le \frac{l(k+1-l)}{k+1}+\frac{4}{5}$$

For odd $k\ge 4(t-1)$ and $l:=\frac{k+1}{2}$, we have:

$$\begin{array}{cc}\hfill t\le \frac{l(k+1-l)}{k+1}+\frac{4}{5}& \iff t\le \frac{{(k+1)}^2/4}{k+1}+\frac{4}{5}\iff t\le \frac{k+1}{4}+\frac{4}{5}\hfill \\ & \Leftarrow t\le \frac{4t-3}{4}+\frac{4}{5}\iff 0\le \frac{-3}{4}+\frac{4}{5}\iff 0\le \frac{1}{20}\hfill \end{array}$$

For even $k\ge 4(t-1)$ and $l:=\frac{k}{2}$, we have:

$$\begin{array}{cc}\hfill t\le \frac{l(k+1-l)}{k+1}+\frac{4}{5}& \iff t\le \frac{\frac{k^2}{4}+\frac{k}{2}}{k+1}+\frac{4}{5}\iff t\le \frac{k^2+k}{4(k+1)}+\frac{k}{4(k+1)}+\frac{4}{5}\hfill \\ & \Leftarrow t\le \frac{k}{4}+\frac{1}{4}\frac{4}{5}+\frac{4}{5}\iff t\le \frac{k}{4}+1\Leftarrow t\le t-1+1\hfill \end{array}$$

☐

In the remainder of this work, we provide more insight into the structure of tree SE graphs for the extreme vertex destroyer. The next theorem says that in a tree with only one max-sep vertex (and $n\ge 8$), there is always an improving swap, so it cannot be an SE. The main concepts are that having a single max-sep vertex makes the destroyer very predictable and that swapping to a leaf, that leaf (which will have degree two in the new graph) can become max-sep only under specific conditions.

Theorem 6.

There is no SE tree with $n_{\max }=1$, provided that $n\ge 8$.

Proof. 

Let $T=(V,E)$ be an SE tree with $n_{\max }=1$ and $u\in V_{\max }$. It is clear that u is a cut-vertex, otherwise G is two-connected, and thus, $n_{\max }=n$. Denote $K_1,\dots ,K_k$, with $k\ge 2$, the components of $T-u$ ordered by non-decreasing sizes $|K_1|\le |K_2|\le \dots \le |K_k|$. For convenience, denote $n_i:=|K_i|$ for each i.

Let $v\in K_1$ and $uv\in E$ and $w\in K_2$ with $deg(w)=1$. We consider $T^{\prime }:=T+(v,u,w)$, that is we detach $K_1$ from u and re-attach it to a leaf of $K_2$. The situation is depicted in Figure 5.

Then, ${rel}^{\prime }(w,v)=rel(u,v)$ and ${rel}^{\prime }(w,v)>{rel}^{\prime }(w^{\prime },v)$ for all $w^{\prime }\ne w$, and so, we have an improvement for v whenever $V_{\max }^{\prime }$ contains at least one vertex distinct from w. The latter is the case if ${sep}^{\prime }(w)\le {sep}^{\prime }(u)$. Using (1), we compute:

$$\begin{array}{cc}\hfill {sep}^{\prime }(w)\le {sep}^{\prime }(u)& \iff n^2-1-n_1^2-{(n-n_1-1)}^2\le n^2-1-{(n_1+n_2)}^2-\sum _{i=3}^k{n}_i^2\hfill \\ & \iff n_1^2+{(n-n_1-1)}^2\ge {(n_1+n_2)}^2+\sum _{i=3}^k{n}_i^2\hfill \\ & \iff {(n-n_1-1)}^2\ge 2n_1{n}_2+\sum _{i=2}^k{n}_i^2\hfill \\ & \iff {\left(\sum _{i=2}^k{n}_i\right)}^2\ge 2n_1{n}_2+\sum _{i=2}^k{n}_i^2\hfill \\ & \iff \sum _{2\le i<j\le k}{n}_i{n}_j\ge n_1{n}_2\hfill \end{array}$$

(∗)

Now, Condition (∗) is true if $k\ge 3$, since $n_1\le n_3$.

Hence, we may assume that $k=2$. Let x be the only vertex in $N(u)\cap K_2$. If $deg(x)\ge 3$, then:

$$\begin{array}{cc}\hfill sep(x)& \ge n^2-1-1-{(n_2-2)}^2-{(n_1+1)}^2\hfill \\ & =n^2-1-1-n_2^2+4n_2-4-n_1^2-2n_1-1\hfill \\ & =sep(u)-1+4n_2-4-2n_1-1\hfill \\ & =sep(u)+2(2n_2-n_1)-6\hfill \\ & \ge sep(u)+2n_2-6\ge sep(u)\hfill \end{array}$$

The last step is true since $n_2\ge (n-1)/2>3$. We conclude that $deg(x)\le 2$. Since $n\ge 8$, there is $y\in N(x)\setminus \{u\}$ with $deg(y)\ge 2$. We consider $T^{\prime }:=T+(u,x,y)$, as shown in Figure 6. We have:

$$\begin{array}{cc}\hfill {sep}^{\prime }(u)<{sep}^{\prime }(y)& \Leftarrow n_1^2+n_2^2>1+{(n_2-2)}^2+{(n_1+1)}^2\hfill \\ & \iff 0>1-4n_2+4+2n_1+1\iff 0>2(n_1-2n_2)+6\hfill \\ & \iff 0>n_1-2n_2+3\Leftarrow n_2>3\hfill \end{array}$$

Since the last statement is true, we know that $V_{\max }^{\prime }=\{y\}$; hence, ${\mathcal{C}}^{\prime }(u)=n_2<n-1=\mathcal{C}(u)$. ☐