Welcome to MathOverflow

Question

1

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

flag	asked Sep 6 at 19:17 Chuck 378●5●11

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

Patricia Hersh · Accepted Answer · 2012-09-06 19:26:26Z UTC

4

This is the domination number of the graph.

Here's a wikipedia article:

en.wikipedia.org/wiki/Dominating_set

answered Sep 6 at 19:26

Patricia Hersh
2,685●1●9●21

	To stress the point further, this is not a coloring concept at all. – Felix Goldberg Sep 6 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 at 20:53

Graph Theory Terminology Question

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.