# Probability for a graph algorithm

Let $$G = (V, E)$$ a graph. A 'dominant set' $$W ⊆ V$$is a set of nodes, so that for each node $$v \in V$$ holds that either $$v$$ itself or a neighbor of $$v$$ is contained in $$W$$. Assume that $$G$$ has minimum degree at least $$d > 1$$, i.e. each node $$v \in V$$ has degree $$deg(v) ≥ d$$.

The algorithm consists of two rounds. In the first round we mark each node independently from the other nodes with probability $$p$$. In the second round we look at each node $$v \in V$$ , if neither $$v$$ nor any of its neighbours were marked in the first lap, we mark $$v$$ .

Let $$X$$ be the number of knots marked in the first round. So $$E(X) = |V|*p$$, because $$X \sim Bin(|V|,p)$$, right ?

Let $$v ∈ V$$any (but fixed) node. If think the probability that neither v nor one of the neighbors of v was marked in the first round would be $$(1-p)^{deg(v)}$$ right ? But how can i finde a upper bound which is only dependent from $$d$$ and $$p$$ (and not from $$v$$).

Let $$Y$$ be the number of knots marked in the second round. How can i finde a upper bound for $$E(Y)$$.

## 1 Answer

The probability of being selected in the second round is $$(1-p)^{\text{deg}(v)\color{red}{+1}}$$.

Use the fact that $$\deg v \ge d$$ to conclude that $$(1-p)^{\deg v+1}\le (1-p)^{d+1}$$. Then $$EY\le |V|(1-p)^{d+1}$$.