CERTIFIED VERTEX COVERING NUMBER OF A GRAPH
Far East Journal of Mathematical Sciences (FJMS) · 11.04.2026 · 143 (4) · 1229-1248
DOI: 10.17654/0972087126071 ↗Kurz gefasst
Fachartikel in der Zeitschrift Far East Journal of Mathematical Sciences (FJMS), online erschienen am 11.04.2026. Verfasst von Amil-Shab S. Sappari und 1 weiteren Autor:innen. Die Arbeit nennt 14 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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
Zitieren
APA
Sappari, A. S., & Jr., S. R. C. (2026). CERTIFIED VERTEX COVERING NUMBER OF A GRAPH. Far East Journal of Mathematical Sciences (FJMS), 143(4), 1229-1248. https://doi.org/10.17654/0972087126071
Vancouver
Sappari AS, Jr. SRC. CERTIFIED VERTEX COVERING NUMBER OF A GRAPH. Far East Journal of Mathematical Sciences (FJMS). 2026;143(4):1229-1248. doi:10.17654/0972087126071
BibTeX
@article{Sappari2026,
author = {Sappari, Amil-Shab S. and Jr., Sergio R. Canoy},
title = {CERTIFIED VERTEX COVERING NUMBER OF A GRAPH},
journal = {Far East Journal of Mathematical Sciences (FJMS)},
year = {2026},
volume = {143},
number = {4},
pages = {1229--1248},
doi = {10.17654/0972087126071}
}
EUVIMED