About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
The minimum number of edges in graphs with prescribed paths
Abstract
Let M be an m-by-n matrix with entries in {0,1,⋯, K}. Let C(M) denote the minimum possible number of edges in a directed graph in which (1) there are m distinguished vertices called inputs, and n other distinguished vertices called outputs; (2) there is no directed path from an input to another input, from an output to another output, or from an output to an input; and (3) for all 1 ≤i ≤m and 1 ≤j ≤n, the number of directed paths from the i-th input to the j-th output is equal to the (i,j)-th entry of M. Let C(m,n,K) denote the maximum of C(M) over all m-by-n matrices M with entries in {0,1,⋯, K}. We assume (without loss of generality) that m ≥n, and show that if m=(K+1)0(n) and K=220(m), then C(m,n,K)= H/log H + 0(H/log H), where H=mnlog(K + 1) and all logarithms have base 2. The proof involves an interesting problem of Diophantine approximation, which is solved by means of an unusual continued fraction expansion. © 1979 Springer-Verlag New York Inc.