Domination and Edge Domination in Trees

Abstract

Let G=(V,E) be a simple graph. A set S⊆V is a dominating set if every vertex in V∖S is adjacent to a vertex in S. The domination number of a graph G, denoted by γ(G) is the minimum cardinality of a dominating set of G. A set D⊆E is an edge dominating set if every edge in E∖D is adjacent to an edge in D. The edge domination number of a graph G, denoted by γ′(G) is the minimum cardinality of an edge dominating set of G. We characterize trees with domination number equal to twice edge domination number.