Given a (non-multi)graph $G$ let $N_G$ be the least number of nodes that must be colored (by a single color) such that every other node in $G$ shares an edge with at least one colored node. (I am only interested in the case where $G$ is an $n \times n$ grid, where such an $N_G$ obviously always make sense - I don't know what constraints (or their names) must be put on $G$ in general for $N_G$ to make sense, but assume 'obvious' ones.)

Is there a technical, graph-theoretic term for $N_G$?

  • $\begingroup$ I definitely wouldn't tag the question "graph-colorings." $\endgroup$ Commented Sep 7, 2012 at 5:30

1 Answer 1


This is the domination number of the graph.

Here's a wikipedia article:


  • $\begingroup$ To stress the point further, this is not a coloring concept at all. $\endgroup$ Commented Sep 6, 2012 at 19:44
  • $\begingroup$ @Felix Goldberg: good point, though perhaps he just found this to be a convenient language in which to explain his question. $\endgroup$ Commented Sep 6, 2012 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.