# Graph Theory Terminology Question

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

-
I definitely wouldn't tag the question "graph-colorings." –  Douglas Zare Sep 7 '12 at 5:30

This is the domination number of the graph.

Here's a wikipedia article:

en.wikipedia.org/wiki/Dominating_set

-
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