PARTITIONED GRAPHS AND DOMINATION RELATED PARAMETERS

Abstract

Let $G$ be a graph of order $n \geq 2$ and $n_1,n_2,..,n_k$ be integers such that $1 \leq n_1 \leq n_2 \leq ..\leq n_k$ and $n_1 + n_2 +..+ n_k = n$. Let for $i=1,..,k$: ${\cal A}_i \subseteq {\cal K}_{n_i}$ where ${\cal K}_m$ is the set of all pairwise non-isomorphic graphs of order $m$, $m = 1,2,..$. In this paper we study when for a domination related parameter $\mu$ (such as domination number, independent domination number and acyclic domination number) is fulfilled $\mu (G) = \mu (\cup_{i=1}^k <V_i, G>)$ for all vertex partitions $\{V_1, V_2,..,V_k\}$, $k \geq 2$, of a vertex set of $G$ such that $<V_i, G>$ is isomorphic to some a member of ${\cal A}_i$, $i=1,2,..,k$. In the process several results for acyclic domination vertex critical graphs are presented. Results for independence number of double vertex graphs are obtained.