Given a set D of nonnegative integers, we derive the asymptotic number of graphs with a givenvnumber of vertices, edges, and such that the degree of every vertex is in D. This generalizes existing results, such as the enumeration of graphs with a given minimum degree, and establishes new ones, such as the enumeration of Euler graphs, i.e. where all vertices have an even degree. Those results are derived using analytic combinatorics.
Other related problems include the enumeration of graphs with a given degree sequence ( @cite_11 ), the enumeration of symmetric matrices with nonnegative coefficients and constant row sum ( @cite_16 ), and the enumeration of graphs with degree parities, investigated by @cite_5 .
@cite_5 @cite_16 @cite_11
2054891628 1997698259
Counting formulae are obtained for the numbers of labelled (p,q)-multigraphs with any even number n of points of odd degree and p-n points of even degree. Similar results are obtained for multigraphs of strength s, and in this case for the sum over the number q of lines. These sums are much less simple if s is even than if s is odd. However, it is shown that for s fixed, and p -> , the asymptotic value does not depend on the parity of s. Abstract Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: (i) each row sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled graphs.