O'Reilly logo

Statistical and Machine Learning Approaches for Network Analysis by Subhash C. Basak, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 img denote a family of bipartite graphs. Then, the corresponding trivariate generating function is the formal power series

img

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

Further, we make use of the notation [xm]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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required