A problem on blocking probabilities in connecting networks
Fan Chung, F. K. Hwang · Networks · 1977
Abstract We begin with a three‐stage linear graph in which the first stage has a single node u and the third stage a single node v. The second stage has k independent nodes, each of which is connected by one link to u and to v. In general, we can form a (2n+1)‐stage linear graph recursively by letting each node in the second stage of a three‐stage linear graph be replaced by a copy of a (2n‐1)‐stage linear graph. A link can either be in the busy state or the idle state. We assume that the states of each link are mutually independent and that any link between stage i and stage i + 1 has the probability I.z of being idle. The nodes u and v are said to be connectable if there exists at least one path from u to v with no busy link. Let P(u, v) denote the probability of such a path existing. Further, let N(2n+1, k) denote the set of (2n+1)‐stage linear graphs whose center stages have k nodes. In this paper, we determine the size of N(2n+1, k). We also give the linear graph in N(2n+1, k) which has the largest P(u, v) and the one which has the smallest. We then show how our results apply to a recent problem in connecting networks.