A Generalization of Takagi's Theorem on Optimal Channel Graphs

A graph is called a multistage graph if its vertex set can be partitioned into subsets Vs, for some number s, and its edge set into subsets Ei,..., Es-1 such that Ei connects V,- with V,+i. A channel graph, also called a linear graph, 5 is a multistage graph with the properties that (i) each of the first and the last stages consists of a single vertex (denoted by / and 0 respectively); (ii) for any vertex ^ / or 0, 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 switch to a fixed output switch can usually be studied as a channel graph by taking each switch as a vertex and each link as an edge. In a switching network, a link can be in either one of two states, busy or idle, depending on whether it is part of a connection carrying a call. A path from a fixed input switch to a fixed output switch is blocked if 171 (a) Fig. 1--Channel graphs in Takagi's theorem.