Changing of the domination number of a graph: edge multisubdivision and edge removal. (English) Zbl 1463.05420

Summary: For a graphical property \(\mathcal{P}\) and a graph \(G\), a subset \(S\) of vertices of \(G\) is a \(\mathcal{P}\)-set if the subgraph induced by \(S\) has the property \(\mathcal{P}\). The domination number with respect to the property \(\mathcal{P}\), denoted by \(\gamma_{\mathcal{P}}(G)\), is the minimum cardinality of a dominating \(\mathcal{P}\)-set. We define the domination multisubdivision number with respect to \(\mathcal{P}\), denoted by \(\text{msd}_{\mathcal{P}}(G)\), as a minimum positive integer \(k\) such that there exists an edge which must be subdivided \(k\) times to change \(\gamma_{\mathcal{P}} (G)\). In this paper
we present necessary and sufficient conditions for a change of \(\gamma_{\mathcal{P}}(G)\) after subdividing an edge of \(G\) once,
we prove that if \(e\) is an edge of a graph \(G\) then \(\gamma_{\mathcal{P}}(G_{e,1})<\gamma_{\mathcal{P}}(G)\) if and only if \(\gamma_{\mathcal{P}}(G-e)<\gamma_{\mathcal{P}}(G)\) (\(G_{e,t}\) denotes the graph obtained from \(G\) by subdivision of \(e\) with \(t\) vertices),
we also prove that for every edge of a graph \(G\) we have \(\gamma_{\mathcal{P}}(G-e)\leq\gamma_{\mathcal{P}}(G_{e,3})\leq\gamma_{\mathcal{P}}(G-e)+1\), and
we show that \(\text{msd}_{\mathcal{P}}(G)\leq 3\), where \(\mathcal{P}\) is hereditary and closed under union with \(K_1\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: DOI arXiv