Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
Articles in Press
2023
09
10
Well ve-covered graphs
14622
10.22049/cco.2023.28186.1469
EN
Razika
Boutrig
Faculty of Economic Sciences and Management, University of Boumerdes, Algeria
Mustapha
Chellali
LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
0000-0001-5231-6195
NacĂ©ra
Meddah
LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270,
Blida, Algeria
Journal Article
2022
12
23
A vertex $u$ of a graph $G=(V,E)$ <em>ve-</em>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 <em>ved-</em>set for short) if every edge of $E$ is <em>ve</em>-dominated by at least one vertex in $S$. A <em>ved</em>-set is independent if its vertices are pairwise non-adjacent. The independent <em>ve</em>-domination number $i_{ve}(G)$ is the minimum cardinality of an independent <em>ved</em>-set and the upper independent <em>ve</em>-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 <em>ve</em>-covered graphs. We show that recognizing well <em>ve</em>-covered graphs is co-NP-complete, and we present a constructive characterization of well <em>ve</em>-covered trees.
https://comb-opt.azaruniv.ac.ir/article_14622_6165a82d2ed9db6dfc8bf158a220335d.pdf