4

I was trying to solve this prisoner puzzle in the Guardian.

We can create a graph where the nodes are the 16 possible combinations of four coins, and there is an edge between A and B iff starting from position A, you can flip a single coin to obtain position B. In fact, this graph turns out to be the hypercube graph $Q_4$.

Then, to solve the puzzle, we have to find a 4-colouring of $Q_4$ such that for every node A and every colour $c$, there is a node B of colour $c$ adjacent to A. In other words, each node has a neighbour of any given colour. There are many such colourings - for example, treating the positions as 4-bit binary numbers, we can do $\min(x,15-x) \bmod 4$.

My question is: is there a name for such a colouring, or for a graph admitting such a colouring? Has this notion been studied at all in the literature?

Jordan Mitchell Barrett
  • 1,857
  • 6
  • 18

1 Answers1

5

There is a closely related and more well-studied concept: domatic number.

A dominating set in a graph $G$ is a subset $U \subset V(G)$ such that every vertex of $G$ is either contained in $U$, or has a neighbor in $U$.

We can extend this to coloring graphs by analogy. An ordinary (proper) coloring of a graph is a partition of the vertices into independent sets: the set of all vertices of a color must be a independent set (where no vertices are adjacent), and the color classes are a partition of the vertices. A domatic partition of a graph is a partition of the vertices into dominating sets.

From here, the domatic number is the maximum number of dominating sets in a domatic partition. It is the maximum number rather than the minimum number, unlike the ordinary notion of graph coloring, because finding a domatic partition gets harder as you increase the number of colors.

A domatic partition of the hypercube would solve an easier version of the puzzle in the Guardian: one in which we have to flip up to one coin, but leaving all coins as they are is a valid move.

What we want for the Guardian puzzle is a stronger notion of dominating sets: a set $U$ such that every vertex of $G$, whether or not it's contained in $U$, has a neighbor in $U$. Such a variant has been considered in research: it is called a total dominating set or a strongly-dominating set.

So if we want a version of domatic number that requires the sets in the partition to be total dominating sets, we might call it a total domatic number.

This is a somewhat more obscure notion (by which I mean that it doesn't have a Wikipedia page) but it has been studied (under the name you'd expect, no less). It appears to have been first introduced in the paper Total domination in graphs by Cockayne, Dawes, and Hedetniemi.

Misha Lavrov
  • 142,276