EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

CERTIFIED VERTEX COVERING NUMBER OF A GRAPH

Amil-Shab S. Sappari, Sergio R. Canoy Jr.

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →