Fractional Vertex Cover Reliability of Graphs

Proof. Let $G$ and $H$ be graphs with ${\mathrm{fvc}}_{i,j}(G)\le {\mathrm{fvc}}_{i,j}(H)$ for all $i,j$. Let $0\le p,q\le 1$ and consider that by equation (1), $$\begin{array}{}\text{(2)}& \begin{array}{rl}\mathrm{FRel}(G;p,q)& =\sum _{i=0}^n\sum _{j=0}^{n-i}{\mathrm{fvc}}_{i,j}(G)p^i{q}^i(1-p-q{)}^{n-i-j}\\ & \le \sum _{i=0}^n\sum _{j=0}^{n-i}{\mathrm{fvc}}_{i,j}(H)p^i{q}^i(1-p-q{)}^{n-i-j}\\ & =\mathrm{FRel}(H;p,q).\end{array}\end{array}$$ Moreover, in this case if there is some $i,j$ such that ${\mathrm{fvc}}_{i,j}(G)<{\mathrm{fvc}}_{i,j}(H)$, then the inequality (2) holds strictly and we conclude $G$ is less reliable than $H$. 

Proof. Assume $G\in \mathfrak{F}$ is such that ${\mathrm{fvc}}_{i,j}(G)\le {\mathrm{fvc}}_{i,j}(H)$ for all $i,j$ and $H\in \mathfrak{F}$. Then it follows from Lemma 1 that $\mathrm{FRel}(G;p,q)\le \mathrm{FRel}(H;p,q)$ for all $H\in \mathfrak{F}$ and $0\le p,q\le 1$, thus making $G$ a least reliable graph of $\mathfrak{F}$.

The proof that $G$ is a most optimal graph of $\mathfrak{F}$ if ${\mathrm{fvc}}_{i,j}(G)\ge {\mathrm{fvc}}_{i,j}(H)$ for all $i,j$ and all $H\in \mathfrak{F}$ is nearly identical. 

Proof. Consider that all fractional vertex covers of $G$ are also fractional vertex covers of $G-e$. Thus ${\mathrm{fvc}}_{i,j}(G)\le {\mathrm{fvc}}_{i,j}(G-e)$ for all $i,j$. Moreover, consider the fractional vertex cover of $G$ in which the endpoints of $e$ are assigned weight $0$, and all other vertices $1$. As no edge is incident to both of the vertices with weight $0$, this is a fractional vertex cover of $G-e$, however applying the same weights to vertices in $G$ fails to be a fractional vertex cover as the weights on endpoints of $e$ sum to $0$. Thus ${\mathrm{fvc}}_{n-2,0}(G)<{\mathrm{fvc}}_{n-2,0}(G-e)$, and by Lemma 1 $G$ is less reliable than $G-e$. 

Proof. Let $S$ be the set of all vertices which receive the weight $0$. First note that $S$ must form an independent set in $G$ and the probability that all vertices in a set $S$ get the same weight $0$ is $(1-p-q{)}^{|S|}$. To cover the edges incident to vertices in $S$, all vertices in $N_G(S)$ must be of weight $1$, giving a probability of $p^{|N_G(S)|}$. Every other vertex in $V(G)\setminus N_G[S]$ can then be either of value $1$, or of value $\frac{1}{2}$ which gives a probability of $(p+q{)}^{|n–N_G[S]|}$. All of these conditions must occur for each independent set of vertices that can take on the value of $0$ in order for G to be reliable, so they are multiplied and then each case of a unique independent set is added together to cover every way in which $G$ can be reliable. Thus, we obtain the result. 

Proof. Let $S$ consists of all vertices which get weight $1$. By definition, every vertex outside of $S$ must get weight $0$ or $\frac{1}{2}$. Since there are no isolated vertices, if some vertex $v$ gets weight $0$ then it must be in $N(S)$ and all neighbors of $v$ must be in $S$. The subset of vertices that have weight $0$ must then be elements of some $U\in \xi (S)$. This leaves the remaining vertices to be of weight $\frac{1}{2}$, of which there are $n–|S|–|U|$. Every vertex of weight $0$ must be adjacent to some vertex of weight $1$ in $S$, and so all ways to get a fractional vertex cover are represented by allowing these zeroes to be some subset $U$ of $\xi (S)$. This leaves the remaining vertices to be of weight $\frac{1}{2}$, of which there must be $n–|S|–|U|$ of them. This leaves a summation across all ways to have $S$, of which there is a probability $p^{|S|}$, and then this is multiplied by all the ways a reliable vertex cover could be completed, of which there are $U\in \xi (S)$ ways where we have the probability of $(1–p–q{)}^{|U|}{q}^{n–|S|-|U|}$. 

Proof. We calculate the fractional reliability by conditioning on vertices which get weight $\frac{1}{2}$. If $S$ consists of all vertices of weight $\frac{1}{2}$, then all all vertices in $N_G(s)$ must get weight $1$, and so we have the probability $p^{|S|}{q}^{|N_G(S)\setminus S|}$. Every edge incident to some vertex in $N_G(S)$ is covered and no vertex outside $S$ gets weight $\frac{1}{2}$. So, given these conditions, the probability that the subgraph $G\setminus N_G[S]$ is reliable is equal to vertex cover reliability of $G\setminus N_G[S]$. 

Proof. The probability that $G$ is reliable and the vertex $u$ gets weight $1$ (respectively $0$) is equal to $p\mathrm{FRel}(G\setminus u;p,q)$ (respectively $(1-p-q)p^r\mathrm{FRel}(G\setminus N[u];p,q)$). The probability that $G$ is reliable given that vertex $u$ gets weight $\frac{1}{2}$ is equal to the probability that $G\setminus u$ is reliable and no vertex in $N_G(u)$ gets weight $0$. Since $N(u)$ is a clique, at most one vertex in $N(u)$ may get weight $0$ when $G\setminus u$ is reliable. The probability that $G\setminus u$ is reliable and a given vertex $v\in N(u)$ gets weight $0$ is equal to $(1-p-q)p^{|N(v)\setminus \{u\}|}\mathrm{FRel}(G\setminus N[v];p,q)$. Thus, $\mathrm{FRel}(G\setminus u;p,q)-\sum _{v\in N(u)}(1-p-q)p^{|N(v)\setminus \{u\}|}\mathrm{FRel}(G\setminus N[v];p,q)$ gives the probability that $G\setminus u$ is reliable and no vertex in $N_G(u)$ gets weight $0$. 

Proof. The probability that $G\vee H$ is reliable and no vertex gets weight $0$ is equal to $(p+q{)}^n$. If some vertex $v$ of $G$ gets weight $0$, then, in order to cover edges from $v$ to $H$, all vertices of $H$ must get weight $1$. The probability that $G$ is reliable with at least one vertex weight $0$ is equal to $\mathrm{FRel}(G,p,q)-(p+q{)}^{n_1}$. Hence, the probability that $G\vee H$ is reliable and at least one vertex of $G$ gets weight is equal to $p^{n_2}(\mathrm{FRel}(G;p,q)-(p+q{)}^{n_1})$. Similarly, the probability that $G\vee H$ is reliable and at least one vertex of $H$ gets weight is equal to $p^{n_1}(\mathrm{FRel}(H;p,q)-(p+q{)}^{n_2})$. 

Proof. Let $w$ be the new vertex which is adjacent to both $u$ and $v$ in $H$. The probability that $H$ is reliable and the vertex $w$ gets weight $1$ is equal to $\mathbb{P}(w\to 1)\mathrm{FRel}(H|w\to 1)=p\mathrm{FRel}(G\setminus e)$, as $w$ does not cover any edge other than $uw$ and $vw$. If $w$ gets weight $0$, then both $u$ and $v$ must get weight $1$ in order for $H$ to be reliable and in this case all edges incident to $u$ or $v$ are covered. So, the probability that $H$ is reliable and $w$ gets weight $0$ is equal to $\mathbb{P}(w\to 0)\mathrm{FRel}(H|w\to 0)=(1-p-q)p^2\mathrm{FRel}(G\setminus \{u,v\})$. Lastly, the probability that $H$ is reliable and the vertex $w$ gets weight $\frac{1}{2}$ is equal to $q\mathrm{FRel}(H|w\to \frac{1}{2})$. So, it remains to compute $\mathrm{FRel}(H|w\to \frac{1}{2})$. $$\begin{array}{rl}\mathrm{FRel}(H|w\to \frac{1}{2})& =\mathbb{P}(G\text{is reliable and neither }u\text{ nor }v\text{ receives weight }0)\\ & =\mathrm{FRel}(G)-\mathbb{P}(G\text{ is reliableand exactly one of }u\text{ or }v\text{ gets weight }0)\\ & =\mathrm{FRel}(G)-(1-p-q)\sum _{x\in \{u,v\}}{p}^{|N_G[x]|}\mathrm{FRel}(G\setminus N_G[x])\end{array}$$ and the last equality follows because all neighbors of a zero weighted vertex must receive weight $1$ in order for the graph to be reliable. 

Proof. In a complete graph $K_n$, non-empty independent sets are precisely the singletons, that is $\mathfrak{I}(G)\setminus \varnothing =\{\{v\}:v\in V(G)\}$. For each nonempty $S\in \mathfrak{I}(G)$, we have $|S|=1$, $|N_G(S)|=n-1$ and $|N_G[S]|=n$ and $|\varnothing |=0$, $|N_G(\varnothing )|=0$. Thus, the result follows from Theorem 1. 

Proof. Let $u$ be a leaf vertex of $P_n$ and let $v$ be the unique neighbor of $u$. The probability that $P_n$ is reliable and $u$ has weight $1$ is equal to $\mathbb{P}(u\to 1)\mathrm{FRel}(P_n;p,q|u\to 1)=p\mathrm{FRel}(P_{n-1};p,q)=p\mathrm{FRel}(P_{n-1};p,q)$ because $u$ covers the edge $uv$. Similarly, the probability that $P_n$ is reliable and $u$ has weight $0$ is equal to $p(1-p-q)p\mathrm{FRel}(P_{n-2};p,q)$ because this case requires the vertex $v$ to have weight $1$, and so both edges incident to $v$ are covered by $v$. Lastly, the event that $u$ has weight $\frac{1}{2}$ and $P_n$ is reliable occurs if and only if $u$ has weight $\frac{1}{2}$, $v$ has non-zero weight and $P_n\setminus u$ is reliable. Considering the complementary event, we find that the probability that $P_n\setminus u$ is reliable and $v$ has weight $0$ is equal to $\mathrm{FRel}(P_{n-1})-p(1-p-q)\mathrm{FRel}(P_{n-3};p,q)$. Thus, the probability that $P_n$ is reliable and $u$ has weight $\frac{1}{2}$ is equal to $q(\mathrm{FRel}(P_{n-1};p,q)-p(1-p-q)\mathrm{FRel}(P_{n-3};p,q))$. 

Proof. Let $e=uv$ be an edge in $C_n$. First observe that $C_n$ is reliable if and only if $C_n\setminus e$ is reliable and the sum of weights of $u$ and $v$ is at least $1$. We will consider the event that $C_n\setminus e$ is reliable but the sum of weights of $u$ and $v$ is less than $1$.

The probability that $C_n\setminus e\cong P_n$ is reliable and both $u$ and $v$ get weight $0$ is equal to $p^2(1-p-q{)}^2\mathrm{FRel}(P_{n-4};p,q)$ because weight $0$ on $u$ and $v$ requires their neighbors in $C_n\setminus e$ to receive weight $1$.

Next, consider the case when $u$ gets weight $0$, $v$ gets weight $\frac{1}{2}$ and $C_n\setminus e$ is reliable. In this case the neighbor of $u$ in $C_n\setminus e$ is required to receive weight $1$, and the neighbor of $v$ in $C_n\setminus e$, say $v^{\prime }$, may get either $\frac{1}{2}$ or $1$. If $v$ gets weight $1$, the fractional reliability is equal to $p^{2}q(1-p-q)\mathrm{FRel}(P_{n-4};p,q)$. If $v$ gets weight $\frac{1}{2}$, then the problem reduces to the fractional reliability of $P_{n-3}$ with one leaf having weight $\frac{1}{2}$, and the latter can be calculated by using the last line in the proof of Theorem 7. Thus, the probability that $C_n\setminus e$ is reliable with the given vertex weights is equal to $p{q}^2(1-p-q)\left[q(\mathrm{FRel}(P_{n-4};p,q)-p(1-p-q)\mathrm{FRel}(P_{n-6};p,q))\right]$. Now, $\mathbb{P}(u\to 0,v\to \frac{1}{2},C_n\setminus e\text{isreliable})=\mathbb{P}(u\to \frac{1}{2},v\to 0,C_n\setminus e\text{is reliable})$. Thus, $$\begin{array}{rl}\mathrm{FRel}(C_n;p,q)& =\mathrm{FRel}(P_n;p,q)-p^2(1-p-q{)}^2\mathrm{FRel}(P_{n-4};p,q)-2p^{2}q(1-p-q)\mathrm{FRel}(P_{n-4};p,q)\\ & -2p{q}^2(1-p-q)\left[q(\mathrm{FRel}(P_{n-4};p,q)-p(1-p-q)\mathrm{FRel}(P_{n-6};p,q))\right]\end{array}$$ and the result follows after the simplification of the above. 

Proof. Let $G$ and $G^{|}$ be as specified. Let $P$ be the path $v_1,\dots ,v_k$. We use Transformation A to show that there is a non-surjective injection from $i,j$-fractional vertex covers of $G^{|}$ to $i,j$-fractional vertex covers of $G$. We then show that for some $i,j$ and $i,j$-fractional vertex cover of $G$, there is no preimage for it among $i,j$-fractional vertex covers of $G^{|}$.

Let ${\mu }^{|}:V(G)\to \{0,\frac{1}{2},1\}$ be a fractional vertex cover of $G^{|}$. We consider two cases depending on whether ${\mu }^{|}(v_1)+{\mu }^{|}(u)\ge 1$.
Case 1. ${\mu }^{|}(v_1)+{\mu }^{|}(u)\ge 1$.

The only edge in $G$ which is not in $G^{|}$ is $v_{k}u$. Because in this case this edge is covered by ${\mu }^{|}$, we map ${\mu }^{|}$ to $\mu$ with $\mu ={\mu }^{|}$.
Case 2. ${\mu }^{|}(v_1)+{\mu }^{|}(u)<1$.

Let $\mu :V(G)\to \{0,\frac{1}{2},1\}$ be defined by $$\mu (w)=\{\begin{array}{ll}{\mu }^{|}(v_{k-i+1})& w=v_i\\ {\mu }^{|}(w)& \text{otherwise}\end{array}.$$ We claim that $\mu$ is an $i,j$-fractional vertex cover of $G$. To prove this, we verify all edges of $G$ are covered by $\mu$. Because ${\mu }^{|}(w)=\mu (w)$ if $w\ne v_i$ for any $i$, all edges not incident to any $v_i$ have the same weights under $\mu$ as they do under ${\mu }^{|}$, hence $\mu$ covers all edges not incident to $P$. Similarly, we can verify that for some edge $v_i{v}_{i+1}$ in $P$, $$\mu (v_i)+\mu (v_{i+1})={\mu }^{|}(v_{k-i+1})+{\mu }^{|}(v_{k-i})\ge 1,$$ and hence $\mu$ covers $P$.

It remains to verify the edges incident to $v_k$ are covered by ${\mu }^{|}$. Since ${\mu }^{|}$ is an $i,j$-fractional vertex cover of $G^{|}$, and by assumption, $${\mu }^{|}(v_1)+{\mu }^{|}(u)\ge 1>{\mu }^{|}(v_k)+{\mu }^{|}(u).$$ Further, this implies $${\mu }^{|}(v_1)>{\mu }^{|}(v_k)$$ and $$\mu (v_k)>\mu (v_1).$$ Hence all edges $v_{k}w$ present in both $G^{|}$ and $G$ are covered in $G$. Finally, consider that for $u{v}_k$, the only edge in $G$ which is not in $G^{|}$, $$\mu (v_k)+\mu (u)={\mu }^{|}(v_1)+{\mu }^{|}(u)\ge 1.$$ Therefore $\mu$ is an $i,j$-fractional vertex cover of $G$.

$${\mu }_1(v_1)+{\mu }_1(u)\ge 1>{\mu }_2(v_1)+{\mu }_2(u),$$ Now we show that any ${\mu }_1$ that is an image of the injection and as described in Case 1, is different than any ${\mu }_2$ which is an image of the injection and is as described in Case 2. Suppose ${\mu }_1$ and ${\mu }_2$ are such $i,j$-fractional vertex covers. Consider that $${\mu }_1(v_1)+{\mu }_1(u)\ge 1>{\mu }_2(v_1)+{\mu }_2(u),$$ hence ${\mu }_1\ne {\mu }_2$ for any ${\mu }_1$ and ${\mu }_2$, as desired.

Now we describe, for some $i,j$, an $i,j$-fractional vertex cover of $G$ that is not the image of the injection.

To this end, we define $$\mu (w)=\{\begin{array}{ll}0& w=v_1\\ \frac{1}{2}& w\in N_G(v_k)\setminus \{v_{k-1}\}\\ 1& \text{otherwise}\end{array}.$$

We claim $\mu$ is a fractional vertex cover of $G$. To wit, the only vertex with weight $0$ is $v_1$, and its only neighbor, $v_2$, has weight $1$. All other edges of $G$ are incident to two vertices with weight at least $\frac{1}{2}$ and are therefore covered by $\mu$. Further, $\mu$ is not a fractional vertex cover of $G^{|}$ as $\mu (v_1)+\mu (u)=\frac{1}{2}$. Therefore, if $\mu$ is the image of a cover of $G^{|}$, it must be a cover ${\mu }_2$ as described in Case 2.

But then the preimage of $\mu$ must have had the weights on $v_1,\dots ,v_k$ reversed; that is, assuming ${\mu }^{|}$ is the preimage of $\mu$ then

$${\mu }^{|}=\{\begin{array}{ll}0& w=v_k\\ \frac{1}{2}& w\in N_G(v_k)\setminus \{v_{k-1}\}\\ 1& \text{otherwise}\end{array}.$$ Since ${\mathrm{deg}}_G(v_k)$ was assumed to be at least $3$, there is some $x\in N_G(v_k)\setminus \{v_{k-1},u\}$. Consider that $v_{k}x\in E(G^{|})$, however $${\mu }^{|}(v_k)+{\mu }^{|}(x)=\frac{1}{2},$$ and hence ${\mu }^{|}$ is not a fractional vertex cover of $G^{|}$. Therefore, $\mu$ is a fractional vertex cover of $G$ which is not the image of any fractional vertex cover of $G^{|}$. Therefore, by Lemma 1 we conclude $G$ is strictly more reliable than $G^{|}$.