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 ${\mathrm{m}\mathrm{s}\mathrm{d}}_{\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)\le {\gamma }_{\mathcal{P}}(G_{e,3})\le {\gamma }_{\mathcal{P}}(G-e)+1$, and \item {(d)} we show that ${\mathrm{m}\mathrm{s}\mathrm{d}}_{\mathcal{P}}(G)\le 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