The Connection Patterns of Two Complete Binary Trees
Fan Chung, Frank K Hwang · SIAM Journal on Algebraic and Discrete Methods · 1980
We consider the class of channel graphs which can be viewed as compositions of two copies, right and left, of a complete binary tree with terminal nodes of the right tree connected to distinct terminal nodes of the left tree. We study the connection patterns of the two binary trees to minimize the blocking probability of the resulting channel graphs. We show that the connection patterns given by Ikeno are not optimal in general and in fact no optimal connection patterns exist for such graphs with more than 9 stages. We present new connection patterns which uniquely possess certain optimal properties.