Optimal domination in graphs
E. J. Cockayne, Stephen T. Hedetniemi · IEEE Transactions on Circuits and Systems · 1975
Graph theoretic techniques provide a convenient tool for the investigation of communication networks. Here a communication network is represented by a nonoriented linear graph, in which the edges represent communication links and the vertices represent cities. A transmitting group is a set of cities which, acting as transmitting stations, can transmit messages to every city in the network. Stated graph theoretically, a transmitting group is a dominating set, i.e., a set of verticesDhaving the property that any vertex not inDis adjacent to at least one vertex inD. The problem of finding disjoint dominating sets in a graph is studied, in particular, the domatic numberd(G)of a graphGis defined as the maximum order of a partition of the vertices ofGinto dominating sets.