MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
I definitely wouldn't tag the question "graph-colorings." – Douglas Zare Sep 7 '12 at 5:30
up vote 5 down vote accepted

This is the domination number of the graph.

Here's a wikipedia article:

share|cite|improve this answer
To stress the point further, this is not a coloring concept at all. – Felix Goldberg Sep 6 '12 at 19:44
@Felix Goldberg: good point, though perhaps he just found this to be a convenient language in which to explain his question. – Patricia Hersh Sep 6 '12 at 20:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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