Trees and unicyclic graphs with large fair domination number

Abstract

A fair dominating set (FD-set) in a graph G is a dominating set 5 such that all vertices not in 5 are dominated by the same number of vertices from S. The fair domination number of G, denoted fd(G), is the ninimumcardinality of an FD-set of G. Caro et al. [Discrete Mathematics 312(2012), 2905-2914] showed that fd(T) ≤ n/2 for any tree T of order n ≥ 2, and characterized all trees T of order n with fd(T) = n/2. We first characterize all trees T of order n with fd(T) = [n/2]. We then prove that fd(G) ≤ (n +1)/2 for any unicyclic graph G of order n, and characterize all unicyclic graphs G of order n with fd(G) = (n + l)/2. © 2019 Utilitas Mathematica Publishing Inc.. All rights reserved.