7 - Dominating sets

Summary

Veni, vidi, vici.

Julius Caesar

Every network N, with underlying graph G, has one or more dominating sets. Historically, this concept originated with von Neumann in his pioneering work with Morgenstern (1944) on the theory of games. In game theory, a given game may have several strategies deciding which move to make in any given game situation. A strategy is said to dominate another one if the person using the first strategy defeats his opponent using the second one in a two-person game. This was formalized to domination in digraphs by Richardson (1953) and studied by Harary and Richardson (1959).

Ore (1962) generalized the concept of domination in digraphs to graphs G. This is entirely analogous to the domination of the 64 squares of a conventional chessboard by Queens. This Queen domination problem was mentioned in Chapter 1. In particular, the placing of eight Queens on a chessboard so that no Queen threatens (dominates) any other Queen was completely solved by Euler in the eighteenth century.

Ore defined a node v in G as dominating itself and all nodes adjacent to it, that is, v dominates its closed neighborhood N[v]. Domination in graphs is now the most active area of research in graph theory (Laskar and Walikar 1981; Hedetniemi and Laskar 1990).

For our present purposes, every island network has some dominating set of islands. We now use the combinatorial model of domination in graphs to describe local political hierarchies in the Caroline Islands in Micronesia, alliance structures in the Tuamotu Islands in Polynesia, and pottery monopolies in two trade networks in Melanesia.