TY - JOUR

T1 - On the relationship between the diameter and the size of a boundary of a directed graph

AU - Jimbo, Shuji

AU - Marouka, Akira

PY - 1994/6/10

Y1 - 1994/6/10

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

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

KW - Boundaries

KW - Combinatorial problems

KW - Diameter

KW - Expanding graphs

KW - Linear functions

UR - http://www.scopus.com/inward/record.url?scp=0028449812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028449812&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(94)00044-1

DO - 10.1016/0020-0190(94)00044-1

M3 - Article

AN - SCOPUS:0028449812

SN - 0020-0190

VL - 50

SP - 277

EP - 282

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -