Statistical and Machine Learning Approaches for Network Analysis

7.3 Enumerating Bipartite Graphs

In this section, we review the generating functions that enable us to count the number of graphs of certain type respectively to calculate asymptotic approximations of these numbers. Note that similar results for nonbipartite graphs are well known, see, for example, Refs. [13, 3]. In contrast, only few results concerning bipartite graphs can be found in the literature. However, trees and unicyclic components have been studied recently, see also Ref. [15].

Let denote a family of bipartite graphs. Then, the corresponding trivariate generating function is the formal power series

where and denote the number of nodes of first and second kind and denotes the number of edges of .

Further, we make use of the notation [x^m]A(x) to extract the mth coefficient of a power series A(x), that means

We start counting all bipartite graphs without restrictions to the type ...