A Note on the Fair Domination in Trees

Abstract

A dominating set in a graph \( G \) is a subset \( S \) of vertices such that any vertex not in \( S \) is adjacent to some vertex of \( S \). The domination number, \( \gamma(G) \), of \( G \) is the minimum cardinality of a dominating set. A dominating set of cardinality \( \gamma(G) \) is called a \( \gamma(G) \)-set. A fair dominating set in a graph \( G \) (or FD-set) is a dominating set \( S \) such that all vertices not in \( S \) are dominated by the same number of vertices from \( S \); that is, every two vertices not in \( S \) have the same number of neighbors in \( S \). The fair domination number, \( fd(G) \), of \( G \) is the minimum cardinality of an FD-set. A fair dominating set of \( G \) of cardinality \( fd(G) \) is called an \( fd(G) \)-set. We say that \( fd(G) \) and \( \gamma(G) \) are \emph{strongly equal} and denote by \( fd(G) \equiv \gamma(G) \), if every \( \gamma(G) \)-set is an \( fd(G) \)-set. In this paper, we provide a constructive characterization of trees \( T \) with \( fd(T) \equiv \gamma(T) \).