Domination-related parameters in rooted product graphs (Q5964910): Difference between revisions

The rooted product \(G\circ H\) of graphs \(G\) and \(H\) w.r.t.\ a selected, fixed vertex \(v\) of \(H\), is constructed as follows. For each vertex \(x\) of \(G\) construct a copy \(H_x\) of \(H\), where \(v_x\) is the vertex of \(H_x\) corresponding to \(v\), and identify \(v_x\) with \(x\). In this extensive paper numerous domination-type invariants are bounded on rooted product graphs in terms of corresponding invariants of the factors. In some cases, exact results are also obtained. As a typical result it is proved that for the standard domination number \(\gamma\) one has \(\gamma(G\circ H) \in \{ |V(G)| \gamma(H), |V(G)|(\gamma(H)-1)+\gamma(G)\}\). Other domination numbers (DNs) studied are Roman DN, independent DN, connected DN, convex DN, weakly connected DN, and super DN. It should be remarked that the notation \(G\circ H\) used for the root product of \(G\) and \(H\) w.r.t.\ the root \(v\) of \(H\) is not specific enough as different roots may lead to non-isomorphic rooted products (with the same factors \(G\) and \(H\)).