Structural Domination of Graphs

Abstract

In a graph $G=(V,E)$, a set $S$ of vertices (as well as the subgraph induced by $S$) is said to be dominating if every vertex in $V\setminus S$ has at least one neighbor in $S$. For a given class $\mathcal{D}$ of connected graphs, it is an interesting problem to characterize the class $Dom(\mathcal{D})$ of graphs $G$ such that each connected induced subgraph of $G$ contains a dominating subgraph belonging to $\mathcal{D}$. Here we determine $Dom(\mathcal{D})$ for $\mathcal{D}=\{P_1,P_2,P_5\}$, $\mathcal{D}=\{K_t\mid t\ge 1\}\cup \{P_5\}$, and $\mathcal{D}=$ {connected graphs on at most four vertices} (where $P_t$ and $K_t$ denote the path and the complete graph on $t$ vertices, respectively). The third theorem solves a problem raised by Cozzens and Kelleher [$Discr.Math.$ 86 (1990), 101-116]. It turns out that, in each case, a concise characterization in terms of forbidden induced subgraphs can be given.