Common domination perfect graphs

Abstract

A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex that does not belong to $S$ is adjacent to a vertex in $S$. The domination number $\gamma (G)$ of $G$ is the minimum cardinality of a dominating set of $G$. The common independence number ${\alpha }_c(G)$ of $G$ is the greatest integer $r$ such that every vertex of $G$ belongs to some independent set of cardinality at least~$r$. The common independence number is squeezed between the independent domination number $i(G)$ and the independence number $\alpha (G)$ of $G$, that is, $\gamma (G)\le i(G)\le {\alpha }_c(G)\le \alpha (G)$. A graph $G$ is domination perfect if $\gamma (H)=i(H)$ for every induced subgraph $H$ of $G$. We define a graph $G$ as common domination perfect if $\gamma (H)={\alpha }_c(H)$ for every induced subgraph $H$ of $G$. We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs.

11 pages, 2 figures