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


FB1 Graphs and Networks 2
June 11, 2021  10:45 AM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.