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

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 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 [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.

No credit card required