Comparisons on Blocking Probabilities for Regular Series Parallel Channel Graphs

Comparisons on Blocking Probabilities for Regular Series Parallel Channel Graphs By D. Z. Du and F. K. HWANG (Manuscript received January 19,1982) We give a sufficient condition for one regular series parallel channel graph to be superior to another with the same number of stages. The main mathematical tools used for doing this are the recently developed results on majorization over a partial order. I. INTRODUCTION An s-stage channel graph is a graph whose vertices can be partitioned into s subsets (stages) Vi, V2, · · · , Vs, with V and V8 each containing a single vertex (called the source and the sink, respectively), and whose edges can be partitioned into s -- 1 subsets Ei, E2, · · ·, Es-1 such that (i) Edges in Ei connect vertices in V, to vertices in Vi+i, (ii) Each vertex in V,, 1 i s, is connected to at least one vertex in each of V,_i and Vi+i. A channel graph is regular if for each i, the numbers of edges in Ei-1 and Ei coincident to a vertex in V, are independent of which vertex is chosen. A series combination of an s-stage channel graph G and a f-stage channel graph if is a union of G and H into an (s + t -- 1)-stage channel graph, with the sink of G identified with the source of H. A parallel combination of two s-stage channel graphs is a union of these two graphs into another s-stage channel graph with the source and the sink of one graph being identified with the source and the sink, respectively, of the other graph. A channel graph is series parallel if it is either an edge or is constructable from two smaller series parallel channel graphs by either a series or a parallel combination.