Keywords

Dynamic processes that model the diffusion of information through a social network have received considerable interest recently: they capture for instance “word of mouth” effects occurring in viral marketing, where the information is only revealed to a small group of persons initially, who subsequently share it with their friends and so. Similarly, we can think of cascading effects in finance, where an institute might default if a certain number of business partners fail (cp. [2, 9, 12, 13] and the references therein).

In this article we study the r-neighbor bootstrap percolation process. Here we are given an undirected graph \(G=(V,E)\) and an integer \(r\ge 1\). Every vertex is either active or inactive. We say a set A of vertices is active if all vertices in A are active. The vertices that are active initially are called seeds, and the set of seeds is denoted by \(A_0\). If vertices become active thereafter we also refer to them as infected. A contagious process evolves in discrete rounds. The set of active vertices in round \(i>0\) is

$$A_i=A_{i-1}\cup \{v:|N(v)\cap A_{i-1}|\ge r\},$$

where N(v) is the set of neighbors of v. That is, a vertex becomes active irrevocably in a given round if it has at least r active neighbors. We refer to r as the threshold. Let \(\langle A_0 \rangle \) be the set of nodes that will eventually become infected if we activate \(A_0\).

FormalPara Definition 1

Given \(G=(V,E)\), a set \(A_0\subseteq V\) is called contagious if \(\langle A_0 \rangle =V\). In words, activating \(A_0\) results in the infection of the entire vertex set. The size of the smallest contagious set is denoted by m(G, r). For a contagious set \(A_0\), the number of rounds until total infection is the smallest integer t with \(A_t = V\).

The term bootstrap percolation is used sometimes to model the case where the seeds are chosen independently at random. In this work we use this term also with respect to the deterministic selection of a contagious set. Bootstrap percolation was first studied by statistical physicists [8]. Since then, this model has found applications in many fields. Furthermore, various questions related to bootstrap percolation have been examined for a large variety of graphs including hypercubes [4], grids [5, 6], several models of random graphs [3, 7, 11], and expanders [10].

A natural question is to determine for a given integer k, what combinatorial properties of graphs ensure that the minimum size of a contagious set is at most k. Such a characterization seems difficult even for \(k=2\) (and \(r=2\)). Indeed the family of all graphs with a contagious set of size two include, for example, cliques, bipartite cliques (with both sides larger than one), and binomial random graphs with edge probability \(p \ge n^{-1/2+\epsilon }\) [11].

Previous works have examined the connection between m(G, k) and the degree sequence of G [1, 16]. Here we continue this line of investigation and study two basic (and interrelated) graph parameters: the minimum degree and edge cardinality. More concretely, our goal is to determine what conditions on these parameters imply that \(m(G,r)=k\) where k is small compared to the number of vertices in G, and \(r \le k\). We study the cases that \(r=k\) or \(r=2\).

How large does the minimum degree have to be in order to guarantee a contagious set of size two, if all thresholds are two? We prove that \(n{\slash }2\) suffices, where n is the number of vertices. A graph with this property is called Dirac graph. Note that this condition on the minimum degree is the best possible: if the minimum degree is \(n{\slash }2-1\), then G might be disconnected implying that \(m(G,2)>2\) (provided that G has at least three vertices). We also prove the existence of a contagious set of size two for Ore graphs. Ore graphs are a generalization of Dirac graphs, where each pair of nonadjacent vertices u, v obeys \(\mathrm {deg}(u)+\mathrm {deg}(v)\ge n\). Similarly to Dirac graphs, they have been studied in the context of Hamiltonicity.

Contagious sets may vary in the number of rounds they require in order to infect the whole graph (e.g., [15]). For Dirac graphs which are not isomorphic to two cliques of equal size connected by a perfect matching, we are able to derive upper bounds on the number of rounds required to infect the whole of G. More specifically, we show that for such graphs, all subsets of three nodes are contagious, and that any such subset will infect the whole graph in at most three rounds. Observe that it is easy to determine the family of all contagious sets in the Dirac graph consisting of two cliques connected by a perfect matching (as well as the number of rounds until all nodes are infected).

A classic question in graph theory is to determine the minimum number of edges in an n-vertex graph G that ensures that G possesses a monotone graph property. Here, we examine extremal questions related to the existence of small contagious sets.

FormalPara Definition 2

Given integers \(n \ge k \ge r\), we denote by M(n, k, r) the maximum number of edges in an n vertex graph G, where G satisfies \(m(G,r)>k\).

First we study M(n, k, k): a necessary condition for a graph \(G=(V,E)\) of \(n>k\) vertices to satisfy \(m(G,k)=k\) is that G is connected. Here we show that the minimum number of edges that guarantees connectivity is also sufficient to ensure \(m(G,k)=k\) for \(n \ge 2k+2\), i.e. we have \(M(n,k,k) = \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) \). Next we consider the case where \(r=2\). For \(k \ll n\), we prove that \(M(n,k,2)=\left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\lfloor \frac{k+1}{2}\rfloor -1\) holds.

Preliminaries. All graphs are undirected. Given a graph \(G=(V,E)\), we will always assume it has n vertices. The degree of a node \(v \in V\) is denoted by \(\mathrm {deg}(v)\). The set of all neighbors of a vertex v are denoted by N(v). For a set \(S \subseteq V\) we shorthand \(\overline{S} := V {\setminus } S\). Given two disjoint sets A, B of vertices, E(A, B) is the number of edges with one endpoint in A and one endpoint in B, and E(A) is the number of edges with both endpoints in A.

1 Contagious Sets in Dirac and Ore Graphs

We focus in this section exclusively on the case \(r=2\). Recall that an n-vertex graph is a Dirac graph if every vertex in the graph is of degree at least \(n{\slash }2\). For an Ore graph \(G = (V,E)\) we have that \(u,v \in V\) with \((u,v) \notin E\) implies \(\mathrm {deg}(u) + \mathrm {deg}(v) \ge n\).

1.1 The Existence of Small Contagious Sets

The upper bound in [1, 16] shows that in a Dirac graph there exists a contagious set of size three. Here we prove that in Dirac graphs there is in fact a contagious set of size two.

The following family of Dirac graphs will be of particular interest: for n even, let \(DC_n\) be the undirected graph composed of two disjoint cliques of size \(\frac{n}{2}\) connected by a perfect matching. Note that a set of two nodes is not contagious in \(DC_n\) only if both nodes are either in the same clique or connected by the perfect matching.

We begin with the following simple lemma.

Lemma 1

Let \(G = (V,E)\) be a Dirac graph and assume that every node has threshold two. If more than \(\frac{n}{2}\) nodes are active, then in the next round all remaining nodes become infected.

Proof

Let \(A \subset V\) with \(|A| > \frac{n}{2}\) denote a set of active, resp. infected nodes. Then every node in \(\overline{A}\) can have at most \(|\overline{A}| - 1 \le \left\lceil \frac{n}{2}\right\rceil - 2\) neighbors outside A. Thus, it must have two neighbors in A, since its degree is at least \(\left\lceil \frac{n}{2}\right\rceil \).    \(\square \)

Lemma 2

Let \(G=(V,E)\) be a Dirac graph that is not \(DC_n\) for some \(n \ge 2\). Then every set of vertices of size three is contagious.

Proof

Let A be a set of active vertices of size k, where \(2<k<n{\slash }2\) holds, and note that then every vertex in A has at least \(n{\slash }2 - k +1\) neighbors in \(\overline{A}\). Thus, A has at least \(k \cdot (n{\slash }2-k+1)\) edges with one endpoint in A and the other one in \(\overline{A}\).

On the other hand, there are only \(n-k\) nodes outside A; in particular, if \(k \cdot (n{\slash }2-k+1) > n-k\) holds, then there must be a node in \(\overline{A}\) that has two neighbors in A and hence will be infected in the next round. The equation \(k \cdot (n{\slash }2-k+1)=n-k\) has exactly two roots: \(k=2\) and \(k=\frac{n}{2}\). Hence every set A satisfying \(3\le |A| < n{\slash }2\) necessarily infects a vertex in \(\overline{A}\). In addition, if a set B has more than \(n{\slash }2\) nodes, then by Lemma 1 it will infect every vertex in \(\overline{B}\).

Hence if a set C of size at least 3 does not infect the whole of G, then it will necessarily infect a set D of size \(n{\slash }2\) eventually: as long as \(|C| < n{\slash }2\), one node in \(\overline{C}\) is infected in the subsequent round. The only way D does not infect an additional vertex is that it is connected by a perfect matching to \(\overline{D}\). In this case by the degree condition both D and \(\overline{D}\) are cliques. This proves the lemma.    \(\square \)

Theorem 1

Every Dirac graph has a contagious set of size two.

Proof

If the graph is a clique, we can activate two arbitrary vertices. Otherwise, the degree constraints guarantee that any two non-adjacent, activated vertices will infect a third vertex. Unless the graph is \(DC_n\), with \(n\ge 2\), Lemma 2 then applies. In case of \(DC_n\) with \(n \ge 2\), in the first round the two nodes that are adjacent to the seeds will be infected, and in the second round all remaining nodes.    \(\square \)

We wish to generalize Theorem 1 to Ore graphs. However, some new ideas are required, as Ore graphs may not share properties of Dirac graphs used in the proof of Theorem 1. For example, Lemma 2 does not extend to Ore graphs. In fact, there exist n-vertex Ore graphs such that there is a selection of up to \(\lfloor \frac{n}{2}\rfloor \) nodes that do not form a contagious set.

Example 1

We construct the graph as follows: the set \(S = \{v_1,v_2,\ldots , v_c\}\) forms a clique. The remaining \(n-c\) nodes also form a clique, and are partitioned into c disjoint groups \(G_1, G_2,\ldots , G_c\). We let \(c \le \lfloor \frac{n}{2}\rfloor \), thus every \(G_i\) is non-empty. Every node in \(G_i\) is adjacent to \(v_i\) but not to any other node in S. Hence S is not a contagious set. Moreover, note that for any pair \((u,v) \in S \times \overline{S}\) we have

$$\mathrm {deg}(u) + \mathrm {deg}(v) = (c - 1 +1) + (n - c - 1 +1) = n,$$

hence we have constructed an Ore graph. Here it is crucial to note that pairs of nodes within S (and in \(\overline{S}\) resp.) are adjacent and hence their degrees are not required to sum up to n in a pairwise manner. Notice that for \(c=\frac{n}{2}\), the constructed graph is \(DC_{n}\).    \(\square \)

Now we show the following.

Theorem 2

Every Ore graph \(G=(V,E)\) has a contagious set of size two.

Proof

For Dirac graphs any three nodes form a contagious set, but we have seen that this statement is not valid for Ore graphs. However, activating three arbitrarily selected nodes with degree \(\frac{n}{2}\) each will infect at least half of the nodes, as we show in Lemma 4.

Interestingly, such an active set of size three can be obtained by activating two nodes only: according to Lemma 3 there are two nodes u, v with degree at least \(\frac{n}{2}\), such that both are adjacent to a third node w of degree at least \(\frac{n}{2}\) as well. Then activating u and v will infect w and subsequently at least half of the nodes.

Thereafter, the infection will reach all nodes unless the graph is isomorphic to \(DC_{n}\). This is proven in Lemma 5. On the other hand, if the graph is isomorphic to \(DC_n\), Theorem 1 implies that \(m(G,2) \le 2\).

Lemma 3

In an Ore graph there exists a vertex w of degree at least \(\frac{n}{2}\) that is adjacent to at least two vertices u, v with \(\mathrm {deg}(u),\mathrm {deg}(v) \ge n{\slash }2\).

Proof

Let S be the set of vertices with degree at least \(\left\lceil \frac{n}{2}\right\rceil \). We want to show that there exists a vertex in S with two neighbors in S.

First we show that S must have size at least \(\left\lfloor \frac{n}{2}\right\rfloor \): if there is a vertex \(x \notin S\), then x has at most \(\left\lceil \frac{n}{2}\right\rceil -1\) neighbors, denoted by N(x). All vertices that do not belong to \(x \cup N(x)\) must belong to S (in order to satisfy the degree constraint for non-adjacent nodes); note that there are at least \(\left\lfloor \frac{n}{2}\right\rfloor \) such nodes outside \(\{x\} \cup N(x)\).

If there is no vertex in S with two neighbors in S, then \(E(S,\overline{S})\ge (\left\lceil \frac{n}{2}\right\rceil -1)\cdot \left\lfloor \frac{n}{2}\right\rfloor \) as \(|S| \ge \left\lfloor \frac{n}{2}\right\rfloor \) and every vertex in S has at least \(\left\lceil \frac{n}{2}\right\rceil -1\) neighbors outside S. Observe that

$$\sum _{v\in \overline{S}}\mathrm {deg}(v)\le |\overline{S}| \cdot \left( \left\lceil \frac{n}{2}\right\rceil -1\right) .$$

Thus, \(|E(\overline{S})|\) is bounded above by the difference of this product on the RHS and the lower bound on \(|E(S,\overline{S})|\):

$$\begin{aligned} |\overline{S}| \cdot \left( \left\lceil \frac{n}{2}\right\rceil -1\right) - \left( \left\lceil \frac{n}{2}\right\rceil -1\right) \cdot \left\lfloor \frac{n}{2}\right\rfloor = \left( \left\lceil \frac{n}{2}\right\rceil -1\right) \cdot \left( |\overline{S}| - \left\lfloor \frac{n}{2}\right\rfloor \right) . \end{aligned}$$
(1)

Recall that we showed \(|\overline{S}|\le \left\lceil \frac{n}{2}\right\rceil \). Thus, the bound given in Eq. (1) is nonnegative only if \(|\overline{S}| \in \left\{ \left\lfloor \frac{n}{2}\right\rfloor , \left\lceil \frac{n}{2}\right\rceil \right\} \), and hence the upper bound equals \(\left\lceil \frac{n}{2}\right\rceil -1\) or 0. But \(\overline{S}\) has to be a clique by choice of S and the degree requirement of Ore graphs. Therefore, the number of edges inside \(\overline{S}\) must be \(\left( {\begin{array}{c}|\overline{S}|\\ 2\end{array}}\right) =\left( {\begin{array}{c}\left\lceil \frac{n}{2}\right\rceil \\ 2\end{array}}\right) \), which contradicts the upper bound of \(\left\lceil \frac{n}{2}\right\rceil -1\) or 0 on the number of edges inside \(\overline{S}\) if \(n>4\) holds.

For \(n \in \{3,4\}\) we recall that every Ore graph has a Hamiltonian cycle [14]; observe that the statement of the lemma follows immediately in this case    \(\square \)

Thus, once we activate u, v, the node w will become infected and then eventually half of the nodes.

Lemma 4

The activation of three vertices with degrees at least \(\frac{n}{2}\) each will infect at least half of the nodes in an Ore graph.

Proof

Let \(A_0\) consist of three vertices of degree at least \(\frac{n}{2}\). Let \(A:=\langle A_0 \rangle \), i.e. the set of nodes that will eventually be active if we activate \(A_0\). Observe that \(A_0 \subseteq A\) holds by definition.

Assume for the sake of contradiction that \(|A|<\frac{n}{2}\) and recall that \(\overline{A} := V {\setminus } A\) is the set of nodes that do not become active. We claim that each of the vertices in \(A {\setminus } A_0\) must have at least one neighbor in \(\overline{A}\): vertices in \(\overline{A}\) have at most one neighbor in A and thus degree at most \(|\overline{A}|\) each. If \(a \in A\) and \(b \in \overline{A}\) are non-adjacent, we have that

$$\mathrm {deg}(a)+\mathrm {deg}(b) \le |\overline{A}|+|A|-1+|N(a)\cap \overline{A}|.$$

As this quantity has to be at least n in an Ore graph and \(|A| + |\overline{A}| = n\) holds, \(N(a)\cap \overline{A}\) must be non-empty.

Each of the nodes in \(A_0\) has degree at least \(\frac{n}{2}\) by assumption of the lemma, and hence each of them has at least \((\frac{n}{2}-(|A|-1))\) neighbors in \(\overline{A}\). Recall that the other \(|A| - 3\) vertices in A must have at least one neighbor in \(\overline{A}\) each. But since each node in \(\overline{A}\) can have at most one neighbor in A, otherwise it would be infected, we get

$$\begin{aligned} |\overline{A}|&\ge 3 \cdot \left( \frac{n}{2}-(|A|-1)\right) +(|A|-3)\\&=3 \cdot \frac{n}{2}-3\cdot |A|+3+|A|-3\\&=\frac{n}{2}+n-2\cdot |A|. \end{aligned}$$

Thus, we have \(|\overline{A}|+2 \cdot |A| =n+|A|\ge n+\frac{n}{2}\) and the desired contradiction \(|A|\ge \frac{n}{2}\) follows.    \(\square \)

Next, we show

Lemma 5

Consider an n-vertex Ore graph that is not equal to \(DC_{n}\). Then any set of three vertices with degree at least \(\frac{n}{2}\) each is a contagious set.

Proof

Pick any three vertices with degree at least \(\frac{n}{2}\) as seed and let A be the set of eventually infected vertices. By Lemma 4 we have \(|\overline{A}|\le |A|\). Again every \(b \in \overline{A}\) is adjacent to at most one node in A, otherwise b would be infected, and hence we have \(\mathrm {deg}(b)\le |\overline{A}|\). Then every node in A that is non-adjacent to some \(b\in \overline{A}\) must have degree at least \(n - |\overline{A}|\) to meet the degree requirement of Ore graphs.

It follows that every vertex \(a \in A\) must have at least one neighbor in \(\overline{A}\): if a is adjacent to all vertices in \(\overline{A}\), the claim holds. If a is non-adjacent to at least one, then we have already shown that a has degree at least \(n - |\overline{A}| = |A|\). Since node a can have only \(|A|-1\) neighbors in A, a must have at least one within \(\overline{A}\).

No vertex in A can have more than one neighbor in \(\overline{A}\), since this would imply the existence of a vertex in \(\overline{A}\) with two active neighbors, as \(|\overline{A}|\le |A|\); but this would contradict the choice of \(\overline{A}\). Thus, each vertex in A has exactly one neighbor in \(\overline{A}\) and we have that \(|A| = |\overline{A}| = n{\slash }2\). Notice that A and \(\overline{A}\) must both be cliques as otherwise two non-adjacent vertices in A (resp., \(\overline{A}\)) would have degree less than \(\frac{n}{2}\) each and thus their degrees add up to less than n contradicting the property of an Ore graph. But then the graph is isomorphic to \(DC_{n}\).    \(\square \)

This concludes the proof of Theorem 2.    \(\square \)

1.2 The Speed of Spreading in Dirac Graphs

In the case of \(DC_n\), it is easy to see that any contagious set actually infects the entire graph in just two rounds. We will now prove a tight bound on the speed of spreading in arbitrary Dirac graphs.

Theorem 3

Let G be a Dirac graph that does not coincide with \(DC_n\) for any \(n \ge 2\), and let \(A_0\) be an arbitrary selection of three vertices. Then the activation of \(A_0\) will infect the whole vertex set within three rounds.

Proof

Recall from Lemma 1 that all nodes will be infected at the end of the subsequent round if \(|A_i| {>} \frac{n}{2}\) holds for any round i. Moreover, if \(|A_1| = \frac{n}{2}\) holds, then the whole graph will be active after the third round, since the graph is not \(DC_{n}\). In particular, any contagious set will infect one new vertex in the first round, hence \(|A_1| \ge 4\) because of \(|A_0| = 3\); thus, we may assume \(\frac{n}{2} {>} 4\), or equivalently \(n {\ge } 9\), and

$$\begin{aligned} |A_1| \le \left\lceil \frac{n}{2} \right\rceil - 1 \end{aligned}$$
(2)

from now on.

Since each node in \(A_1\) has at most \(|A_1| - 1\) neighbors in \(A_1\), it has at least \(\left\lceil \frac{n}{2} \right\rceil {} {-} |A_1| {+} 1\) edges to nodes outside \(A_1\). Moreover, since each node outside \(A_1\) is adjacent to at most one node in \(A_0\), we observe that the neighborhood of \(A_0\) in \(\overline{A}_1\), denoted by N, has size \(|N| \ge |A_0| \cdot \left( \left\lceil \frac{n}{2} \right\rceil - |A_1| + 1 \right) = 3 \cdot \left( \left\lceil \frac{n}{2} \right\rceil - |A_1| + 1 \right) \). Finally, consider the \(|A_1| - 3\) nodes of \(A_1 {\setminus } A_0\) and note that there are at least \(\left( |A_1| - 3\right) \cdot \left( \left\lceil \frac{n}{2} \right\rceil {} {-} |A_1| {+} 1\right) \) edges between \(A_1 {\setminus } A_0\) and \(\overline{A}_1\); we denote the set of these edges by F.

There are \(n {-} |A_1|\) nodes outside \(A_1\). For the sake of contradiction, let us assume now that there are at most \(\left\lfloor \frac{n}{2}\right\rfloor {-} |A_1|\) nodes in \(\overline{A}_1\) that have more than one neighbor in \(A_1\). Then the number of edges between \(\overline{A}_1\) and \(A_1 {\setminus } A_0\) is at most

$$\begin{aligned} (n - |A_1| - |N|) + (|A_1|-3) \cdot \left( \left\lfloor \frac{n}{2}\right\rfloor {-} |A_1|\right) . \end{aligned}$$
(3)

To see this upper bound, first observe that at most \(n - |A_1| - |N|\) edges of F can be placed so that every node in \(\overline{A}_1\) is adjacent to exactly one node in \(A_1\). The second summand follows from the observation that each node in \(\overline{A}_1\) is incident with at most \(|A_1|{-}3\) edges of F.

But this yields the desired contradiction, since we know that there are at least \(\left( |A_1|-3\right) \cdot \left( \left\lceil \frac{n}{2} \right\rceil - |A_1| +1\right) \) edges in F. Subtracting the upper bound on number of edges given by Eq. (3), that was implied by the assumption that there are at most \(\left\lfloor \frac{n}{2}\right\rfloor {-} |A_1|\) nodes in \(\overline{A}_1\) with more than one neighbor in \(A_1\), we obtain

$$\begin{aligned}&\left( |A_1|-3\right) \cdot \left( \left\lceil \frac{n}{2} \right\rceil - |A_1| +1\right) - (n - |A_1| - |N|) - (|A_1|-3) \cdot \left( \left\lfloor \frac{n}{2}\right\rfloor {-} |A_1|\right) \\ \ge&\; |A_1|-3 + |N| - n + |A_1|\\ \ge&\; 2\cdot |A_1| - 3 + 3 \cdot \left( \left\lceil \frac{n}{2} \right\rceil - |A_1| + 1 \right) - n\\ \ge&\; 3 \cdot \left\lceil \frac{n}{2} \right\rceil - |A_1| - n \ge \left\lceil \frac{n}{2} \right\rceil - |A_1| \ge 1, \end{aligned}$$

where the last inequality is implied by Eq. (2). Thus, in \(\overline{A}_1\) there are at least \(\left\lfloor \frac{n}{2}\right\rfloor {+}1 {-} |A_1|\) nodes with at least two neighbors in \(A_1\), and all remaining nodes will be infected in the third round according to Lemma 1.    \(\square \)

Corollary 1

Any contagious set of size two in a Dirac graph infects the entire graph within at most four rounds.

Proof

Any contagious set satisfies \(|A_1|>|A_0|=2\) after the first round; then Theorem 3 gives that the whole vertex set will be infected after three additional rounds.    \(\square \)

We show that the bounds given in Theorem 3 and Corollary 1 are tight.

Example 2

Consider the following graph on the vertex set \(V=\{v_1,\ldots ,v_8\}\): let \(v_1,v_2,v_3\) be a clique, \(v_4\) and \(v_5\) be adjacent to \(v_1\), while \(v_7\) and \(v_8\) are adjacent to \(v_2\). Moreover, let \(v_3\) be adjacent to \(v_4\) and \(v_6\). \(v_4\) and \(v_5\) are adjacent to each other as well as to \(v_7\) and \(v_8\). \(v_7\) and \(v_8\) are adjacent to each other and to \(v_6\). \(v_6\) is also adjacent to \(v_5\). Every vertex has degree at least four. Thus, if \(v_1\) and \(v_2\) are activated, it takes four rounds for the entire graph to be infected. Moreover, if we activate \(v_1\), \(v_2\), and \(v_3\) then it takes three rounds for the entire graph to be infected.    \(\square \)

2 Extremal Number of Edges

What is the maximum number of edges in a graph with n nodes such that there is no contagious set of size k assuming that all nodes have threshold k? We provide the following tight bound for the case \(n\ge 2k+2\).

Theorem 4

Let \(k \ge 1\). For \(n\ge 2k+2\) we have \(M(n,k,k)=\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) \).

Proof

To see \(M(n,k,k)\ge \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) \), note that a clique of \(n-1\) nodes plus an isolated node is a disconnected graph with n nodes and \(\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) \) edges. However, no disconnected graph can have a contagious set of size \(k<n\) when the thresholds are k. In the sequel we show \(M(n,k,k)\le \left( {\begin{array}{c}n-1\\ 2\end{array}}\right) \), i.e. every graph on n nodes with at least \(\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) + 1\) edges has a contagious set of size k if all thresholds are k.

If a set \(S \subseteq V\) with \(|S| = k\) is not contagious for all thresholds equal to k, then there is a set T with \(S \subseteq T\) such that each node in \(\overline{T}\) has at most \(k-1\) neighbors in T; only then the infection does not spread outside of T.

The gist is that there are at least

$$|\overline{T}| \cdot \left( |T| - (k-1)\right) = \left( n - |T|\right) \cdot \left( |T| - (k-1)\right) $$

pairs of nodes in \(T \times \overline{T}\) that are not adjacent. In particular, we claim that if \(|T| \in \{k+1, k+2,..., n-3, n-2\}\) then the number of non-adjacent node pairs is larger than \(n-2\). However, at most \(n-2\) pairs of nodes are not adjacent in a graph with n nodes and at least \(\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) + 1\) edges, since \(\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) + 1 = \left( {\begin{array}{c}n\\ 2\end{array}}\right) - (n-2)\) holds. Thus, if the number of active vertices is at least \(k+1\) and at most \(n-2\), then in the subsequent round at least one more node is infected newly, and therefore the infection does not stop until at least \(n-1\) nodes are active.

Now we prove the claim. First observe that \(f(|T|) = \left( n - |T|\right) \cdot \left( |T| - (k-1)\right) \) is a quadratic function in |T| and has roots \(|T|= n\) and \(|T| = k-1\). In the former case, the process has already infected all nodes, and the latter case cannot occur, since \(S \subseteq T\) and \(|S| = k\). Next we show that f(|T|) is larger than \(n-2\) for values of \(|T| \in \{k+1,\ldots ,n-2\}\). Recall that we assumed \(n \ge 2k + 2\), and observe that the number of non-adjacent pairs in \(T \times \overline{T}\) is minimized for any fixed k by setting \(n = 2k + 2\). Therefore the number of such pairs is at least \((2k+2 - |T|)\cdot (|T| - k + 1)\). On the one hand, if \(|T| = k+1\) holds, then their number is \((k+1) \cdot 2 = 2k+2 = n\). On the other hand, for \(|T| = n-2 = 2k\) their number is \(2 \cdot (k+1) = n\) again. Thus, the claim holds for both values of |T|, and furthermore for all choices of |T| in between, since \(f''(|T|) = -2\) and hence f is concave.

Thus, we focus on \(|T| \in \{k,n-1\}\) in the sequel. First we show how to select \(A_0\) with \(|A_0| = k\) such that \(|A_1| \ge k+1\) holds. If the graph does not contain any node of degree less than k, we pick any node v and choose \(A_0\) to contain k neighbors of v. Then \(v \in A_1\) holds and hence \(|A_1| \ge k+1\).

Now assume there is a node u with degree \(d < k\). Note that any node of degree smaller k is non-adjacent to at least \(n-1 - \frac{n-2}{2} = \frac{n}{2}\) nodes, where we use \(\frac{n-2}{2} \ge k\). Hence there can be at most one such node because there are at most \(n-2\) non-adjacent pairs of nodes in the graph.

Let \(G'\) be the graph after removing u and its d incident edges. Note that the degree of each node in \(G'\) was reduced by at most one due to the removal of u, therefore all degrees in \(G'\) are at least \(k-1\). Hence we pick any node w that was adjacent to u (recall that the graph is connected) and choose \(A_0\) to contain u and \(k-1\) neighbors of w. Then in the first round w will be infected, thus we have \(|A_1| \ge k+1\).

We have already shown that if there are at least \(k+1\) active nodes, then the process does not stop until there are \(n-1\) active nodes. Assume that the process does not infect the last node w. Then w has degree less than k; but in this case w was selected for \(A_0\). Thus, the process cannot stop at \(n-1\) nodes.    \(\square \)

Example 3

Note that the statement of Theorem 4 does not hold for arbitrary \(k\in \{1,\ldots , n-1\}\) if n is fixed. For a clique on n vertices we pick a perfect matching M and delete the edges of M. Let \(k=n{-}1\). Each vertex has degree \(n{-}2\), hence there is no contagious set of size \(n{-}1\).    \(\square \)

For the case that all nodes have threshold two we give in Theorem 5 a tight bound on the number of edges that guarantees the existence of a contagious set of size \(k\ll n\).

Theorem 5

For all \(k\ge 2\) there exists \(n_k\in \mathbb {N}\), such that for all \(n\ge n_k\),

$$M(n,k,2)=\left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\left\lfloor \frac{k-1}{2}\right\rfloor .$$

Due to space restrictions the proof is deferred to the full version of the paper.

We did not attempt to find the exact k(n) for which Theorem 5 holds. It should be noted that certain restrictions on k have to be imposed, as is shown the following example.

Example 4

We construct a family of graphs to demonstrate that

$$M(n,k,2)=\left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\left\lfloor \frac{k-1}{2}\right\rfloor $$

does not hold for arbitrary k and n. Consider for \(k\ge \frac{2n+2}{3}\) a clique on \(n-k\) vertices together with a star on k vertices. All \(k-1\) leaves of the star must be contained in a contagious set and so do two vertices from the clique, so there is no contagious set of size k. However, the number of edges is

$$\begin{aligned}&\left( {\begin{array}{c}n-k\\ 2\end{array}}\right) +(k-1)=\left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\frac{k}{2}+\frac{3k}{2}-(n+1) \\&\qquad \qquad \qquad \qquad \quad \;\;\quad \ge \left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\frac{k}{2} > \left( {\begin{array}{c}n-k+1\\ 2\end{array}}\right) +\left\lfloor \frac{k-1}{2}\right\rfloor . \end{aligned}$$

   \(\square \)

3 Conclusion

We have examined conditions on the minimum degree and the average degree of undirected graphs ensuring the existence of contagious sets of size \(k \ge 2\).

We focused primarily on the case where all thresholds equal two and showed tight bounds on the number of rounds it takes to infect all vertices for graphs whose minimum degree guarantees the existence of a contagious set of size two.

There are several questions that arise from this work. One is to determine the value of M(n, k, r) for all \(n \ge k \ge r\). Another question is to find how large the minimum degree of G needs to be in order to ensure that \(m(G,r)=k\), where \(k\ge r>2\). Finally, it might be of interest to discover additional graph properties implying \(m(G,2)=2\).