Structure and density of sparse crossbar concentrators
E. Gunduzhan, A. Yavuz Oruç · DIMACS series in discrete mathematics and theoretical computer science · 1998
A sparse crossbar (n, m)-concentrator is a bipartite graph with n source and m sink vertices, m ≤ n, in which there exists a matching between every m source vertices and the m sink vertices. In this paper, we investigate the structure, and the density of sparse crossbar (n, m)-concentrators among all 2nm bipartite graphs. We establish that the density of sparse crossbar concentrators is bounded from belowby0.2887 when m = n, from above by 1/e when m = n/2, and it tends to 0 when m =1, as n →∞. We also derive upper and lower bounds on the density of sparse crossbar (n, m)-concentrators for an arbitrary m ≤ n. The lower bounds provide an insight into the structure of sparse crossbar concentrators, while the upper bounds give a partial characterization of bipartite graphs which fail to have a concentrator property.