CERTIFIED VERTEX COVERING NUMBER OF A GRAPH

A set $S \subseteq V(G)$ is a vertex cover of an undirected graph $G$ if for every edge $uv$ in $G$, we must have $u \in S$ or $v \in S$. A vertex cover $S \subseteq V(G)$ is a certified vertex cover (covering) of $G$ if for every $v \in S$, it holds that $|N_G(v) \cap (V(G) \setminus S)|=0$ or $|N_G(v) \cap (V(G) \setminus S)| \geq 2$. The smallest cardinality of a certified vertex covering of $G$, denoted $\beta_{cer}(G)$, is called the certified vertex covering number of $G$. In this paper, we show that given two positive integers $a$ and $b$ such that $2 \leq a \leq b$, there exists a connected graph $G$ such that $\gamma_{cer}(G)=a$ and $\beta_{cer}(G)=b$, where $\gamma_{cer}(G)$ is the certified domination number of $G$. We also characterize the certified vertex covers of the corona, edge corona, and lexicographic product. From these characterizations, we determine a bound or the exact value of the certified vertex covering number of each of these graphs. Received: January 21, 2026Accepted: March 23, 2026