PARTITIONED GRAPHS AND DOMINATION RELATED PARAMETERS

Abstract

Let $G$ be a graph of order $n\ge 2$ and $n_1,n_2,..,n_k$ be integers such that $1\le n_1\le n_2\le ..\le n_k$ and $n_1+n_2+..+n_k=n$. Let for $i=1,..,k$: ${\mathcal{A}}_i\subseteq {\mathcal{K}}_{n_i}$ where ${\mathcal{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\ge 2$, of a vertex set of $G$ such that $<V_i,G>$ is isomorphic to some a member of ${\mathcal{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.