Minimal vertex cover

Question

Definition: Let $G$ be a graph. A subset $C \subseteq V(G)$ is a vertex cover of $G$ if for each $e \in E(G)$, $e\cap C \neq \phi$. If $C$ is minimal with respect to inclusion, then $C$ is called minimal vertex cover of $G$.

Let $G$ be a graph with $V(G)=\{z_1,\ldots,z_n\}$. Let $H$ be the new graph $H$ on new vertices $\{z_{1,1},z_{1,2},\ldots ,z_{n,1},z_{n,2}\} $ and edge set of $H$ be $E(G)=\Big\{ \{z_{a,b},z_{c,d}\} \mid \{z_{a},z_c\} \in E(G) \text{ and } b+d \leq 3\Big\}$.

One can see that if $M_1=\{z_{i_1},\ldots,z_{i_r}\}$ is a minimal vertex cover of $G$ , then $M_2=\{z_{i_1,1},z_{i_1,2},\ldots,z_{i_r,1},z_{i_r,2}\}$ is a minimal vertex cover of $H$.

Is $M_2$ the largest cardinality of minimal vertex cover of $H$?

Answer 1

Not necessarily. E.g., the set $\{z_{i,1}\colon 1\leq i\leq n\}$ is also a minimal vertex cover of $H$ (whenever $G$ has no isolated vertices), and it may have more elements (e.g., if $G$ is a star, and $M_1$ consists of its center).

In fact, all minimal covers of $H$ can be pbtained in the following way. Notice that, if $C_2$ is a cover of $H$, then $C_1=\{z_i\colon z_{i,1}\in C_2\}$ is necessarily a cover of $G$. So, let us start with a (not necesarily minimal) cover $C_1$ of $G$, and include into a sought cover $C_2$ of $H$ all vertices $z_{i,1}$ with $z_i\in C_1$. We need also to include all $z_{j,2}$ which are neighbours of some $z_{k,1}$ with $z_k\notin C_1$.

This constitutes a cover of $H$, but not necessarily a minimal one. Say that a vertex in a covering is necessary if it cannot be removed. Then all vertices $z_{j,2}\in C_2$ are necessary, as well as all vertices corresponding to necessary vertices of $C_1$. On the other hand, a vertex of $C_2$corresponding to unnecessary vertex in $C_1$ is necessary if it has a neighbor $z_{j,2}$ which is not in $C_2$; that neighbor coresponds to another unnecessary neighbor in $C_1$.

Thus, the condition that $C_2$ is monomal is; Each unnecessary vertex in $C_1$ has an unnecessary neighbor.

[EDIT OF ADDENDUM] Sorry, the previous argument was wrong. It showed only that the conjecture from the comment holds whenever each induced subgraph of $G$ has a minimal vertex cover containing at least half of its vertices. However, there exist graphs where each minimal vertex cover has less than a half of vertices, and each such graph is a counterexample to what you wanted.

E.g., take $K_3$, and attach to each its vertex two degree 1 vertices (so we have 9 vertices at all). Each its minimal vertex cover contains two vertices of $K_3$, hence it contains either the third vertex as well, or two its leaves. Hence $M_1$ may contain at most 4 vertices. On the other hand, the graph $H$ admits a minimal vertex cover of 9 vertices, as described above.