1987/05/01 by Ben Johnsen, Eldar Straume · 2 citations
Computer Science · Engineering · Mathematics · #Matrix Theory and Algorithms #graph theory and CDMA systems #Graph theory and applications
paper · pdf · doi:10.1090/s0025-5718-1987-0878703-6
This paper is concerned with the calculation of certain numbers sb(p), b(p,q) related to combinatorial problems and graph theory, p, q are vectors of nonnegative integers, and sb(p) is the number of labelled graphs with vertex degree sequence p, or equivalently, the number of 0-diagonal, symmetric, binary matrices with row sum p.Similarly, b(p, q) is the number of binary rectangular matrices with row sum p and column sum q.The numbers also appear as coefficients in the expansions 11(1 + xxX 11(1 + xy).Explicit (i.e., nonrecursive) formulas for sb(p), b(p,q) are developed, together with an analysis of their complexity.Properties of p (or q), such as max/>,, k Zp, n = #/>, # 0, are incorporated into a numerical invariant which measures the total "cost" (or computing time).The performance of the theory for practical calculations has been thoroughly tested.For example, with suitable restrictions on p one may obtain sb(p) for, say, n = 20 or k = 30.