Fair domination in graphs

Yair Caro, Adriana Hansberg, Michael Henning

Research output: Contribution to journalArticlepeer-review

35 Citations (Scopus)

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 languageEnglish
Pages (from-to)2905-2914
Number of pages10
JournalDiscrete Mathematics
Volume312
Issue number19
DOIs
Publication statusPublished - 6 Oct 2012

Keywords

  • Fair domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Fair domination in graphs'. Together they form a unique fingerprint.

Cite this