B.S.T.J. Briefs: A Counterexample to a Conjecture on the Blocking Probabilities of Linear Graphs

A Counterexample to a Conjecture on the Blocking Probabilities of Linear Graphs by H.W. BERKOWITZ (Manuscript received November 21, 1978) It was conjectured by Chung and Hwang that a series-parallel regular linear graph is superior to another if its degree sequence majorizes the degree sequence of the other. A counterexample to this conjecture is given. The following definitions are taken from Refs. 1 and 2. Consider a tstage linear graph with a source (the vertex of the first stage) and a sink (the vertex of the last stage). All the vertices are arranged in a sequence of stages such that, for each edge, one vertex is in stage i and the other vertex is in stage i + 1, for some i. Each edge is in one of two states, busy or idle. A linear graph is blocked if every path joining the source and the sink contains a busy edge. Assume that any edge connecting a vertex in stage i with a vertex in stage i + 1 has probability Pi of being busy for 1 i t -- 1. For a '£-stage linear graph, the sequence (pi, p2, ··· , Pt-) is called the link occupancies for that graph. One stage linear graph is superior to another if, for any given link occupancies, the blocking probability of the first graph does not exceed that of the second. Let e be an edge from a vertex a in stage i to a vertex b in stage i + 1. Define (e) to be the ratio of the outdegree of a to the indegree of b. A £-stage linear graph is regular if, for each i, 1 i t -- 1, if e and f are any two edges between stage i and stage i + 1, than A( e) = Mf).