Changing of the domination number of a graph: edge multisubdivision and edge removal

Samodivkin, Vladimir

Mathematica Bohemica, Tome 142 (2017) no. 1, pp. 9-20.

Résumé

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 ${\rm 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 \item {(a)} we present necessary and sufficient conditions for a change of $\gamma _{\mathcal {P}}(G)$ after subdividing an edge of $G$ once, \item {(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), \item {(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 \item {(d)} we show that ${\rm msd}_{\mathcal {P}}(G) \leq 3$, where $\mathcal {P}$ is hereditary and closed under union with $K_1$.

Détail

DOI : 10.21136/MB.2017.0009-15

Classification : 05C69
Mots-clés : dominating set; edge subdivision; domination multisubdivision number; hereditary graph property