## 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