A Generalization of Takagi's Theorem on Optimal Channel Graphs
Fan Chung, F. K. Hwang · Bell System Technical Journal · 1978
A channel graph, also called a linear graph,5is a multistage graph with the properties that (i) each of the first and the last stages consists of a single vertex (denoted by I and O respectively); (ii) for any vertex v ≠ I or O, v is adjacent to at least one vertex from the preceding stage and at least one vertex from the following stage. In a switching network, the union of all paths connecting a fixed input terminal to a fixed output terminal can usually be studied as a channel graph by taking each switch as a vertex. In comparing the blocking probabilities of two channel graphs with the same number of stages, we say one is superior to another if its blocking probability is less than or equal to that of the other under any link occupancies. Takagi proved a basic theorem in showing one type of channel graph is superior to another. In this note we present a more powerful result which includes Takagi's theorem as a special case.