Well ev-covered trees

¹ Faculty of Economic Sciences and Management, University of Boumerdes, Boumerdes, Algeria
² LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

^* Corresponding author: m_chellali@yahoo.com

Received: 11 September 2022
Accepted: 7 June 2023

Abstract

An edge in a graph G = (V, E) is said to ev-dominate the vertices incident to it as well as the vertices adjacent to these incident vertices. A subset F ⊆ E is an edge-vertex dominating set (or simply, ev-dominating set) if every vertex is ev-dominated by at least one edge of F. The ev-domination number γ_ev(G) is the minimum cardinality of a ev-dominating set of G. An ev-dominating set is independent if its edges are independent. The independent ev-domination number i_ev(G) is the minimum cardinality of an independent ev-dominating set and the upper independent ev-domination number β_ev(G) is the maximum cardinality of a minimal independent ev-dominating set of G. In this paper, we show that for every nontrivial tree T, γ_ev(T) = i_ev(T) ≤ γ(T) ≤ β_ev(T), where γ(T) is the domination number of T. Moreover, we provide a characterization of all trees T with i_ev(T) = β_ev(T), which we call well ev-covered trees, as well as a characterization of all trees T with γ_ev(T) = i_ev(T) = γ(T).