Graph Theory Terminology Question - MathOverflow 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 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 Answer by Patricia Hersh for Graph Theory Terminology Question 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>