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.

  • $\begingroup$ $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. $\endgroup$ Commented Sep 13, 2017 at 3:15
  • $\begingroup$ 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? $\endgroup$
    – bof
    Commented Sep 13, 2017 at 7:48
  • $\begingroup$ I wasn't questioning there validity merely my ability to understand what the question was asking. $\endgroup$
    – Faust
    Commented Sep 13, 2017 at 16:02

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .