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