On Perfect and Quasiperfect Domination in Graphs

Abstract

A subset $S\subseteq V$ in a graph $G=(V,E)$ is a $k$-quasiperfect dominating set (for $k\ge 1$) if every vertex not in $S$ is adjacent to at least one and at most $k$ vertices in $S$. The cardinality of a minimum $k$-quasiperfect dominating set in $G$ is denoted by ${\gamma }_{1k}(G)$. Those sets were first introduced by Chellali et al. (2013) as a generalization of the perfect domination concept and allow us to construct a decreasing chain of quasiperfect dominating numbers $n\ge {\gamma }_{11}(G)\ge {\gamma }_{12}(G)\ge \dots \ge {\gamma }_{1\Delta }(G)=\gamma (G)$ in order to indicate how far is $G$ from being perfectly dominated. In this paper we study properties, existence and realization of graphs for which the chain is short, that is, ${\gamma }_{12}(G)=\gamma (G)$. Among them, one can find cographs, claw-free graphs and graphs with extremal values of $\Delta (G)$.

14 pages, 9 figures

References in corpus (1)

• Perfect domination in rectangular grid graphs

Cited by in corpus (1)

• Perfect and quasiperfect domination in trees