B. Şahin, A. Şahin
An edge e dominates a vertex v, if e is incident to v or e is incident to a vertex which is adjacent to v. A subset D ⊆ E is an edge-vertex dominating set (in simple, ev-dominating set) of a graph G, if every vertex of G is ev-dominated by at least one edge of D. The minimum cardinality of an ev-dominating set is called ev-domination number and denoted by γev(G). In this paper, we study double edge-vertex domination where a subset D ⊆ E is a double edge-vertex dominating set (in simple, double ev-dominating set) of G, if every vertex of V (G) is ev-dominated by at east two edges of D. The double ev-domination number of a graph G is denoted by γdev(G) and it is equal to the minimum cardinality of a double ev-dominating set. We first show that determining the double ev-domination number of bipartite graphs is NP-complete. Moreover, we show that γdev(T ) ≤ γd(T ) for a tree T and we characterize the
trees attaining the equality γdev(T ) = γd(T ).
Keywords: Domination, double domination, double edge-vertex domination
Scheduled
FB1 Graphs and Networks 2
June 11, 2021 10:45 AM
1 - GB Dantzig
