Domination with respect to nondegenerate properties: vertex and edge removal

Samodivkin, Vladimir

Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 75-85.

Résumé

In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property $\mathcal {P}$, denoted by $\gamma _{\mathcal {P}} (G)$, when a graph $G$ is modified by deleting a vertex or deleting edges. A graph $G$ is $(\gamma _{\mathcal {P}}(G), k)_{\mathcal {P}}$-critical if $\gamma _{\mathcal {P}} (G-S) \gamma _{\mathcal {P}} (G)$ for any set $S \subsetneq V(G)$ with $|S|=k$. Properties of $(\gamma _{\mathcal {P}}, k)_{\mathcal {P}}$-critical graphs are studied. The plus bondage number with respect to the property $\mathcal {P}$, denoted $b_{\mathcal {P}}^+ (G)$, is the cardinality of the smallest set of edges $U \subseteq E(G)$ such that $\gamma _{\mathcal {P}} (G-U) >\gamma _{\mathcal {P}} (G)$. Some known results for ordinary domination and bondage numbers are extended to $\gamma _{\mathcal {P}} (G)$ and $b_{\mathcal {P}}^+ (G)$. Conjectures concerning $b_{\mathcal {P}}^+ (G)$ are posed.

Détail

DOI : 10.21136/MB.2013.143231

Classification : 05C69
Keywords: dominating set; domination number; bondage number; additive graph property; hereditary graph property; induced-hereditary graph property