Total edge–vertex domination

¹ Department of Mathematics, Faculty of Science and Letters, Ağrı İbrahim Çeçen University, 04100 Ağrı, Turkey.
² Department of Mathematics, Faculty of Science, Selçuk University, 42130 Konya, Turkey.

^* Corresponding author: shnbnymn25@gmail.com

Received: 7 May 2019
Accepted: 28 January 2020

Abstract

An edge e ev-dominates a vertex v which is a vertex of e, as well as every vertex adjacent to v. A subset D ⊆ E is an edge-vertex dominating set (in simply, ev-dominating set) of G, if every vertex of a graph G is ev-dominated by at least one edge of D. The minimum cardinality of an ev-dominating set is named with ev-domination number and denoted by γ_ev(G). A subset D ⊆ E is a total edge-vertex dominating set (in simply, total ev-dominating set) of G, if D is an ev-dominating set and every edge of D shares an endpoint with other edge of D. The total ev-domination number of a graph G is denoted with γ_ev^t(G) and it is equal to the minimum cardinality of a total ev-dominating set. In this paper, we initiate to study total edge-vertex domination. We first show that calculating the number γ_ev^t(G) for bipartite graphs is NP-hard. We also show the upper bound γ_ev^t(T) ≤ (n − l + 2s − 1)∕2 for the total ev-domination number of a tree T, where T has order n, l leaves and s support vertices and we characterize the trees achieving this upper bound. Finally, we obtain total ev-domination number of paths and cycles.