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$?


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.

  • $\begingroup$ Suppose $M_1$ is the largest minimal vertex cover of $G$. Is $M_2$ the largest minimal vertex cover of $H$? $\endgroup$
    – user177523
    Nov 18 '18 at 9:08
  • 1
    $\begingroup$ Added an answer; hope this is the last reformulation;). $\endgroup$ Nov 18 '18 at 10:00
  • 1
    $\begingroup$ Sorry, the previous addendum was wrong. I've replaced it with a (more) correct one. $\endgroup$ Nov 18 '18 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.