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 \geq 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.