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)$.