most recent 30 from http://mathoverflow.net 2013-05-24T15:45:04Z http://mathoverflow.net/feeds/question/106536 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106536/graph-theory-terminology-question Chuck 2012-09-06T19:17:57Z 2012-09-06T19:26:26Z

<p>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.)</p> <p>Is there a technical, graph-theoretic term for $N_G$?</p>

http://mathoverflow.net/questions/106536/graph-theory-terminology-question/106538#106538 Patricia Hersh 2012-09-06T19:26:26Z 2012-09-06T19:26:26Z

<p>This is the domination number of the graph. </p> <p>Here's a wikipedia article:</p> <p><a href="http://en.wikipedia.org/wiki/Dominating_set" rel="nofollow">en.wikipedia.org/wiki/Dominating_set</a></p>