H-forming sets in graphs Original Research Article

For graphs G and H, a set S⊆V(G) is an H-forming set of G if for every v∈V(G)−S, there exists a subset R⊆S, where |R|=|V(H)|−1, such that the subgraph induced by R∪{v} contains H as a subgraph (not necessarily induced). The minimum cardinality of an H-forming set of G is the H-forming number γ{H}(G). The H-forming number of G is a generalization of the domination number γ(G) because γ(G)=γ{P2}(G). We show that γ(G)⩽γ{P3}(G)⩽γt(G), where γt(G) is the total domination number of G. For a nontrivial tree T, we show that γ{P3}(T)=γt(T). We also define independent P3-forming sets, give complexity results for the independent P3-forming problem, and characterize the trees having an independent P3-forming set.