Optimal domination in graphs

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 vertices having the property that any vertex not in is adjacent to at least one vertex in . The problem of finding disjoint dominating sets in a graph is studied, in particular, the domatic number of a graph is defined as the maximum order of a partition of the vertices of into dominating sets.