Fair domination in graphs
type: Item
instance of: scholarly article
title: Fair domination in graphs
zbMATH Open document ID: 1251.05121
author: Yair Caro
author: Michael A. Henning
author: Adriana Hansberg
published in: Discrete Mathematics
publication date: 2012-09-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/1109.1150
review text: In this paper the authors prove many results about the fair domination number, \(\text{fd}(G)\), of a graph, \(G\). The first main theorem shows that a graph, \(G\) with \(n\geq3\) vertices, none of which are isolated, has \(\text{fd}(G)\leq n-2\) and this bound is sharp. Specializing to trees with \(n\geq2\) vertices, the authors prove that \(\text{fd}(T) \leq n/2\) with equality exactly when the tree is the corona of a tree. Further, they give two conditions equivalent to a tree with \(n\geq 3\) vertices and \(\ell\) leaves having \(\text{fd}(T) < n -\ell\). Another family of graphs that the authors consider are the maximal outerplanar graphs, which are graphs that are triangulations of polygons. They prove that for a maximal outerplanar graph with \(n\geq 3\) vertices, \(\text{fd}(G) < 17n/19\). The final result of the paper gives an inequality for the fair domination number of a disjoint union of graphs. The paper concludes with five open problems about fair domination number. There are a number of other smaller results that are not described here.
reviewed by: Matthew S. Miller
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6081335
zbMATH Keywords: fair domination number
MaRDI profile type: Publication
OpenAlex ID: W2026021893
arXiv ID: 1109.1150
cites work: Large Nearly Regular Induced Subgraphs
cites work: Maximum \(k\)-regular induced subgraphs
cites work: Main eigenvalues and \((\kappa ,\tau )\)-regular sets
cites work: Repetition number of graphs
cites work: Integral graphs and \((k,\tau )\)-regular sets
cites work: Q3626865
cites work: Perfect domination in regular grid graphs
cites work: Perfect domination in rectangular grid graphs
cites work: Q3691778
cites work: Perfect dominating sets in the Cartesian products of prime cycles
cites work: Q4368728
cites work: Q4361572
cites work: Q4949848
cites work: Domination-balanced graphs
DOI: 10.1016/J.DISC.2012.05.006
description: scientific article; zbMATH DE number 6081335