Equivalence domination in graphs

Abstract

For a graph G = (V, E), a subset S ⊆ V (G) is an equivalence dominating set if for every vertex v ∈ V (G) \ S, there exist two vertices u, w ∈ S such that the subgraph induced by {u, v, w} is a path. The equivalence domination number is the minimum cardinality of an equivalence dominating set of G, and the upper equivalence domination number is the maximum cardinality of a minimal equivalence dominating set of G. We explore relationships between total domination and equivalence domination. Then we determine the extremal graphs having large equivalence domination numbers.