ON THE RELATIONSHIP BETWEEN THE DIAMETER AND THE SIZE OF A BOUNDARY OF A DIRECTED GRAPH

A family of expanding graphs is useful to make many kind of networks e fficient, as Ajtai et al. constructed sorting networks of depth 0(log n) with it. On the other hand, Klawe showed that particular families o f directed graphs obtained from a finite number of one-dimensional lin ear functions, which play important roles in constructing some kind of networks or generating random numbers, cannot be families of expandin g graphs. Moreover, Klawe gave a conjecture concerning a lower bound o f the amount of expanding property of these families. Maass gave a par tial answer to the conjecture. In this paper, a theorem that states th e relationship between the diameter and the size of a boundary in a di rected graph is proved. An answer to Klawe's conjecture is also obtain ed from this theorem. The answer is more suitable than Maass's one.