Abstract
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 has the same number of neighbors in S. The fair domination number, fd(G), of G is the minimum cardinality of an FD-set. Among other results, we show that if G is a connected graph of order n<3 with no isolated vertex, then fd(G)≤n-2, and we construct an infinite family of connected graphs achieving equality in this bound. We show that if G is a maximal outerplanar graph, then fd(G)<17n19. If T is a tree of order n<2, then we prove that fd(T)≤n2 with equality if and only if T is the corona of a tree.
Original language | English |
---|---|
Pages (from-to) | 2905-2914 |
Number of pages | 10 |
Journal | Discrete Mathematics |
Volume | 312 |
Issue number | 19 |
DOIs | |
Publication status | Published - 6 Oct 2012 |
Keywords
- Fair domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics