# Vertex cover in a special graph

We say that an undirected graph $$G=(V, E)$$ is special if for every vertex $$v\in V$$ and edge $$\{u, w\}\in E$$, it holds that $$\{v, u\}\in E$$ or $$\{v, w\}\in E$$. In other words, a graph is special if for every vertex $$v$$, the set of the vertices that are not neighbors to $$v$$ is an independent set.

Is the vertex cover problem still hard when restricted to special graphs? I tried considering the standard NP-hardness proof of the vertex cover problem, but the output graph is far from being special.

• Can you share the motivation for this question? In what context did you encounter it? Are you able to credit the original source?
– D.W.
Oct 29, 2021 at 22:45
• I came up with it, just curios whether the problem remains hard for such graphs. They seem to have many edges but perhaps not too many so that the problem remains hard. Oct 30, 2021 at 12:39

To see this, define a relation $$\sim$$ on $$V$$: $$x \sim y$$ if $$\{x,y\} \notin E$$. Clearly $$x \sim x$$, and if $$x \sim y$$ then $$y \sim x$$. If $$x \sim y$$ and $$y \sim z$$ then $$x \sim z$$: indeed, otherwise, $$\{y,z\}$$ is an edge but neither $$\{x,y\}$$ nor $$\{x,z\}$$ are. Thus $$\sim$$ is an equivalence relation. Denoting its equivalence classes by $$V_1,\ldots,V_r$$, the graph is a complete multi-partite graph with parts $$V_1,\ldots,V_r$$.