Certified Vertex Cover of a Graph

Authors

  • Javier Hassan MSU Tawi-Tawi College of Technology and Oceanography
  • Maria Andrea O. Bonsocan
  • Regimar A. Rasid
  • Amil-Shab S. Sappari

DOI:

https://doi.org/10.29020/nybg.ejpam.v17i2.5157

Keywords:

certified set, vertex cover, certified vertex covering set, certified vertex cover number

Abstract

Let $G$ be a graph. Then $Q \subseteq V(G)$ is called a certified vertex covering set of G if $Q$ is a vertex cover of $G$ and every $x \in Q$, $x$ has zero or at least two neighbors in $V(G)\setminus Q$. The certified vertex cover number of $G$, denoted by $\beta_{cer}(G)$, is the minimum cardinality of a certified vertex cover of $G$. In this paper, we investigate this parameter on some special graphs and on the join of two graphs. We characterize certified vertex covering sets in these graphs and we use these results to derive the simplified formulas for solving the said parameter. Moreover, we present some bounds and properties of this parameter.

Downloads

Published

2024-04-30

Issue

Section

Nonlinear Analysis

How to Cite

Certified Vertex Cover of a Graph. (2024). European Journal of Pure and Applied Mathematics, 17(2), 1038-1045. https://doi.org/10.29020/nybg.ejpam.v17i2.5157