Graph with large domination number and high connectivity I am trying to construct a graph with a large domination number, and such that every independent set can be dominated by one vertex. Can anybody help? I can't seem to manage the interplay between the two conditions.
 A: All graphs below are assumed to be finite, simple, and undirected. For a graph $G$ denote by $\Delta(G)$ its maximum vertex degree, by $\alpha(G)$  the maximum size of its (vertex) independent set and by $\operatorname{dom}(G)$  the minimum size of its (vertex) dominating set. Given a graph $G$ construct its supgraph $G’$ as follows. For each maximal independent set $S$ of $G$ we introduce a new vertex $v_S$ of $G’$ adjacent with all vertices from $S$. Also we set that all vertices $v_S$ are mutually adjacent. Let $S’$ be an independent set of $G$. There exists a maximal dominating set $S$ of vertices of the graph $G$ containing all vertices of $S’$ which belong to $G$. Then $v_S$ dominates $S’$. One the other hand, any vertex $v’$ of the graph $G’$ can dominate at most $\alpha(G)$ vertices of $G$ (if $v’\not\in G$) and at most $\Delta (G)+1$ vertices of $G$ (if $v’\in G$). Thus $\operatorname{dom}(G’)\ge |V(G)|/\max\{\alpha(G), \Delta(G)+1\}$. It remains to find a graph $G$  with relatively small both $\alpha(G)$ and $\Delta(G)$. For instance, if $G$ is a union of $k$ mutually disjoint copies of a complete graph $K_k$, then $\alpha(G)=k$ and $\Delta(G)=k-1$. Thus $\operatorname{dom}(G’)\ge k$. (It can be easily shown that $\operatorname{dom}(G’)=k$).
A: Such graph $G$ does not exist since the dominating number must be 1 or 2.
Take a maximal independet set I. Then there exists a vertex $v$ which dominates it.
Suppose $v$ does not dominate the whole graph; then there exists $w$ such that $(v,w) \notin E(G)$. If $\{w,v\}$ is not a dominating set there exist a vertex $x$ such that $x$ is not adyacent to $v$ or $w$. 
Then the the set $A=\{w,v,x\}$ is independent and hence there exist a vertex $y$ that dominates the set $A$  which implies $\{v,y\}$ is a dominating set. ( If not you repeat this process, and assuming it is a finite graph, you will obtain a dominating set with two vertices).
