Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I definitely wouldn't tag the question "graph-colorings." –  Douglas Zare Sep 7 '12 at 5:30
add comment

1 Answer

up vote 4 down vote accepted

This is the domination number of the graph.

Here's a wikipedia article:

en.wikipedia.org/wiki/Dominating_set

share|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
add comment

Your Answer

 
discard

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.