Directed complete bipartite graph decompositions: Indirect constructions

Edge-decompositions of the complete λλ-fold directed graph K⇒n into (uniform) directed complete bipartite subgraphs K⇒a,b form a model for wireless communication in sensor networks. Each node can be in one of three states: asleep (powered down), listening, or transmitting. Communication requires that the sender be transmitting, the destination listening, and no other node near the receiver transmitting. We represent nodes of the network as the vertices of K⇒n, and time slots for communication as blocks of the graph decomposition. A block with out-vertices A and in-vertices B corresponds to a slot in which the nodes in A are transmitting, those in B   are receiving, and all others are asleep. Thus, such a decomposition of λK⇒n guarantees that every ordered pair of nodes in the associated network can communicate in λλ time slots. Additional constraints are needed to minimize interference by a third node. Some recursive constructions for these graph decompositions are established, with particular emphasis on properties minimizing interference.