TY - JOUR
ID - 14622
TI - Well ve-covered graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Boutrig, Razika
AU - Chellali, Mustapha
AU - Meddah, NacĂ©ra
AD - Faculty of Economic Sciences and Management, University of Boumerdes, Algeria
AD - LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
AD - LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270,
Blida, Algeria
Y1 - 2023
PY - 2023
VL -
IS -
SP -
EP -
KW - vertex-edge domination
KW - independent vertex-edge domination
KW - well ve-covered graphs
KW - trees
DO - 10.22049/cco.2023.28186.1469
N2 - A vertex $u$ of a graph $G=(V,E)$ ve-dominates every edge incident to $u$ as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is a vertex-edge dominating set (or a ved-set for short) if every edge of $E$ is ve-dominated by at least one vertex in $S$. A ved-set is independent if its vertices are pairwise non-adjacent. The independent ve-domination number $i_{ve}(G)$ is the minimum cardinality of an independent ved-set and the upper independent ve-domination number $\beta_{ve}(G)$ is the maximum cardinality of a minimal independent ved-set of $G$. In this paper, we are interesting in graphs $G$ such that $i_{ve}(G)=\beta_{ve}(G)$, which we call well ve-covered graphs. We show that recognizing well ve-covered graphs is co-NP-complete, and we present a constructive characterization of well ve-covered trees.
UR - https://comb-opt.azaruniv.ac.ir/article_14622.html
L1 - https://comb-opt.azaruniv.ac.ir/article_14622_6165a82d2ed9db6dfc8bf158a220335d.pdf
ER -