# Question about minimal dominating set

For every integer $k\ge2$ construct a connected graph $G_{2,k}$ that has a minimal dominating set $X$ of cardinality 2 as well as a minimal dominating set $Y$ of cardinality $k$. Explain why $X$ and $Y$ are minimal dominating sets.

A dominating set of a graph $G$ is a set $D\subset V(G)$ such that every vertex of $G$ belongs to $D$ or is adjacent to a vertex that belongs to $D$. A dominating set $D$ is minimal dominating if no proper subset of $D$ is a dominating set.

I think this is saying that a minimal dominating set $D$ is the least number of vertices so that the neighborhood of all of them is $V(G)$.

I haven't managed to find $G_{2,k}$ notation in my textbook my best guess is that it means that the 2 vertices are connected to all the $k$ vertices like in a bipartite graph and perhaps themselves as well?

Could someone take a whack at explaining what is being said/asked here? The two books I have don't have this material in them.

• $G_{2,k}$ is the graph you are supposed to find, not any given family of graphs. Your interpretation of "minimal dominating set" is better known as minimum dominating set. Commented Sep 13, 2017 at 3:15
• The problem statement and definition you quoted are perfectly clear and mean exactly what they sey. Why do you think they must mean something else?
– bof
Commented Sep 13, 2017 at 7:48
• I wasn't questioning there validity merely my ability to understand what the question was asking. Commented Sep 13, 2017 at 16:02

The answer is $K_{2,k}$: the complete bipartite graph with bipartition $\{X,Y\}$ and $|X|=2,|Y|=k$. Each of the bipartitions is a minimal dominating set because removing any vertex in them makes the vertex just removed neither in the dominating set or adjacent to it, the latter because the vertices in a bipartition are disjoint.