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

Samodivkin, Vladimir

Math. Bohem. 142, No. 1, 9-20 (2017).

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

(a)

we present necessary and sufficient conditions for a change of \(\gamma_{\mathcal{P}}(G)\) after subdividing an edge of \(G\) once,

(b)

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),

(c)

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

(d)

we show that \(\text{msd}_{\mathcal{P}}(G)\leq 3\), where \(\mathcal{P}\) is hereditary and closed under union with \(K_1\).

MSC:

05C69

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

dominating set; edge subdivision; domination multisubdivision number; hereditary graph property