Open access peer-reviewed chapter - ONLINE FIRST

Combinatorial Enumeration of Graphs

By Carlos Rodríguez Lucatero

Submitted: May 16th 2019Reviewed: July 24th 2019Published: August 31st 2019

DOI: 10.5772/intechopen.88805

Downloaded: 32

Abstract

In this chapter, I will talk about some of the enumerative combinatorics problems that have interested researchers during the last decades. For some of those enumeration problems, it is possible to obtain closed mathematical expressions, and for some other it is possible to obtain an estimation by the use of asymptotic methods. Some of the methods used in both cases will be covered in this chapter as well as some application of graph enumeration in different fields. An overview about the enumeration of trees will be given as an example of combinatorial problem solved in a closed mathematical form. Similarly, the problem of enumeration of regular graphs will be discussed as an example of combinatorial enumeration for which it is hard to obtain a closed mathematical form solution and apply the asymptotic estimation method used frequently in analytic combinatorics for this end. An example of application of the enumerative combinatorics for obtaining a result of applicability criteria of selection nodes in a virus spreading control problem will be given as well.

Keywords

  • combinatorial graph enumeration
  • generating functions
  • probability

1. Introduction

Enumerating a finite set of objects is one of the most basic tasks that can be done by any person. Anybody begins to do it at first while learning the basic arithmetic operations at school. In a very general setting, to enumerate a finite set of things is to put in bijective relation a finite subset of the natural numbers with the things to be counted. As simple as it can be at first sight, the enumeration of things can become a very interesting mathematical activity when we start to count, for instance, in how many ways can we dispose or can we select the nelements of set in kplaces without repeating them, sometimes allowing repetitions of all of them, or just some of them, etc. That is the starting point of the combinatorics subject. Combinatorics is the field of discrete mathematics that allows us, among other things, to calculate in how many ways some objects can be selected or arranged to comply with any given property.

Within the topic of combinatorial analysis, there is a subfield that is interested in accurately predicting large structured configurations under the analytical method approach and that uses the tool known as generating functions. The analytic combinatorics is devoted to the study of finite structures whose construction follows a certain finite number of given rules. On the other hand, the use of generating functions is a tool that allows to relate discrete analysis proper to discrete mathematics with continuous analysis.

One of the most beautiful and ingenious applications of combinatorial enumeration is the probabilistic method. The probabilistic method is intimately related to the important role that randomness plays in the field of theoretical computer science. The utility and beauty of the probabilistic method consists of being an indirect or nonconstructive proof method. This method has been used successfully during the last 60 years and constitutes one of the most important scientific contributions of the great Hungarian mathematician Erdös [1, 2]. Commonly, this method has been used to prove the existence of a certain mathematical object by showing that if we choose some object of a given class in a random way, the probability that this mathematical object complies with certain property is greater than zero.

The probabilistic method has been used with great success to obtain important results in fields as diverse as number theory, combinatorics, graph theory, linear algebra, computational sciences, or information theory.

One aim of combinatorial analysis is to count the different ways of arranging objects under given constraints. Sometimes the structures to be counted are finite and some other times they are infinite. To enumerate is very important in many scientific fields because it allows to evaluate and compare different solutions to a given problem. For example, in computer science, if I want to compare different algorithms that solve a given kind of information processing problem, it is necessary to enumerate the number of steps taken by each one of them in the worst case and to choose the one whose performance is the best. The task of enumerating things can evolve in complexity to some point that the elementary arithmetical operations are not enough to reach the goal. For that reason many enumeration problems have inspired the most talented mathematicians for developing very ingenious methods for solving them. Some of these techniques for solving combinatorics enumeration problems are going to be exposed in the next section. One very interesting subject of the discrete mathematics is the graph theory. It is in the graph theory where many of the most interesting enumerations of graphs arise that have some given structural property that require the utilization of mathematical tools that facilitate the discovery of closed mathematical forms for the calculation of the number of graphs that accomplish some topological property. In this context it can be important to enumerate how many labeled graphs can be constructed with n vertex or how many connected graphs with n vertex exist, etc. For some of these problems, clever methods have been devised for their calculation that lead to closed mathematical forms by the use of generating functions. For other problems, it is very hard to obtain a closed mathematical form solution, and in that case some asymptotic methods have been developed for estimating a bound when the number of vertex is very large by means of the Cauchy theorem. These mathematical tools are going to be covered in the following sections of the present chapter.

2. Body of the manuscript

The chapter will have the following structure. In Section 3, we will make a quick revision of some mathematical tools that are frequently used for solving combinatorial enumeration problems. The first tool described will be the ordinary generating functions as well as the exponential generating functions. These tools are used when a closed form solution for an enumeration problem can be obtained. The second tool that will be described in this section will be the analytic combinatorics method that is normally used for those enumeration problems whose closed mathematical form are hard to be calculated. The analytic combinatorics techniques allow to estimate an upper bound of that kind of enumeration problems. We take the enumeration of labeled trees as an example of combinatorial enumeration problem that can be solved in a closed mathematical form and make an overview of some different methods devised for that end in Section 4. In Section 5, we roughly describe how the generating functions can be used to solve graph enumeration problems. In Section 6, we take the problem of enumerating regular graphs as an example of a problem whose closed mathematical form is hard to obtain and apply the analytic combinatorics techniques for estimating an upper bound. In Section 7, I give an application of the combinatorial enumeration for proving the almost sure applicability of a node selecting criteria for controlling virus spreading in a complex network. Finally in Section 8, we make some comments about the possible future applications of the combinatorial enumeration methods.

3. Generating functions and analytic combinatorics overview

In this section of the chapter, we are going to make a revision of the basic mathematical tools that have been developed and that facilitate the solution of many combinatorial enumeration problems. We are going to start with some basic conceptual definitions that can be found in many textbooks about this topic. In order to be able to clearly expose the mathematical tools used, it will be necessary to make use of some basic concepts about them that can be consulted more widely in texts such as [3]. One of these basic notions that can be found in [3] is the concept of combinatorial class whose definition is as follows:

Definition 1.1 A combinatorial class is a finite or denumerable set in which a size function is defined, satisfying the following conditions:

  1. The size of an element is a nonnegative integer.

  2. The number of elements of any given size is finite.

On the other hand, it is necessary to know if two combinatorial classes are related in any way which can be determined using the concept of isomorphism and that can be defined as follows:

Definition 1.2 The combinatorial classes Aand Bare said to be (combinatorially) isomorphic which is written ABif and only if their counting sequences are identical. This condition is equivalent to the existence of a bijection from Ato Bthat preserves size, and one also says that Aand Bare bijectively equivalent.

The notion of ordinary generating functions (OGF) as i=0aixiwhere the coefficients aiare elements of the sequence A=a0a1or combinatorial class A. This function is also the generating function of the numbers Anwhose sizes an=cardAnsuch that the OGF of class Aadmits the combinatorial form

Ax=αAxα.E1

This means that the variable x marks size in the generating function. The OGF form (1) can be easily interpreted by observing that the term xn occurs as many times as there are objects in Aof size n. A basic operation that can be defined is the one that allows to extract the coefficient of the term xnin the power series Ax=anxnas follows:

xnn0anxn=an.E2

The concept of generating function can then be defined as:

Definition 1.3 Let be a0,a0,a succession of real numbers. The function

fx=a0+a1x+a2x2+=i=0aixiE3

is the generating function of the given succession.

The idea comes from the development of Newton’s binomial that con be defined as:

Definition 1.4

1+xn=n0+n1x+n2x2++nnxnE4

which is the generating function of the succession

n0,n1,n2,n3,,nn,0,0,0,E5

We can say, for example, that

i=0nxi=1+x+x2+x3++xn=1+xn+11xE6

is the generating function of the succession 1,1,1,,1,0,0,0,where the first n+1terms are equal to 1. The upper limit of the generating function 6 can be extended to which is known as geometric series. This series is known to be convergent if x<1and that case can be defined as

i=0xi=1+x+x2+x3++=11xE7

which is the geometric series of the succession 1,1,1,. One of the nice properties of the generating functions is that they can be easily manipulated due to the fact that they are infinite polynomials.

For instance, if we take the first derivative of the generating function 7, we get

ddx11x=ddx1+x+x2+x3+=1+2x+3x2+4x3+=11x2E8

then 11x2is the generating function of the succession 1,2,3,4,, while x1x2is the generating function of the succession 0,1,2,3,4,. Similarly if we take the first derivative of the generating function x1x2, we get

ddxx1x2=ddx0+x+2x2+3x3+4x4+=x+11x3E9

then x+11x3is the generating function of the succession 12,22,32,, and xx+11x3is the generating function of the succession 02,12,22,32,Other simple manipulations that can be done with the generating functions allow us to cancel some element of an associated succession. For example, if gx=11xand hx=gxx2=11xx2, then hxbecomes the generating function of the succession 1,1,0,1,1,1,. By the other side, if we know that xx+11x3is the generating function of the succession 02,12,22,32,and that x1x2is the generating function of the succession 0,1,2,3,4,, then if we add these two generating functions, we get

xx+11x3+x1x2=2x1x3E10

where 2x1x3becomes the generating function of the succession 0,2,6,12,20,30,42,whose nth element can be expressed as an=n2+n. If we use the coefficient extracting operator defined by 2, we can say that

xn2x1x3=n2+nE11

As an example, let us take the sequence 0,1,1,2,3,5,8,13,21,34,55,know as Fibonacci numbers. This succession can be generated by applying the recurrence relation

Fn+1=Fn+Fn1wheren1,F0=0,F1=1.E12

The goal is to obtain nth element of the succession of numbers generated by 12 that is the coefficient of xn in the expansion of the function

x1xx2E13

as a power series about the origin. The roots of 1xx2are x1=1+52and x2=152. Given that the generating function of the Fibonacci succession is 13, we have that

fx=x1xx2=15111+52x11152xE14

and the nth term of the Fibonacci succession is expressed in closed form as

Fn=1511+52n1152nE15

The calculation of the n-th term of the Fibonacci sequence by using power series allows us to obtain a mathematical closed formula. Because of that we can calculate the n-th term of the Fibonacci sequence in a more efficient way given that the computer program to do it will consist in the direct application of the closed mathematical expression obtained, which is much more efficient than using a computer program based on the application of the Fibonacci recurrence.

In [4] the problem of the various results that can be obtained using generating functions is addressed. The authors of [4] say that by using the tool of generating functions for obtaining the nth element of a succession, sometimes an exact formula can be obtained easily, and if it is not the case, a good estimation of the nth element can be obtained. It can happen also that we get a recurrence formula from where a generating function can be obtained, or it can happen that from the generating function a new recurrence is obtained giving us a deeper understanding about the succession. The use of generating functions provides statistical information about the succession. The authors of [4] also point out that when it is very difficult to mathematically obtain the n-th term of a given sequence as a closed mathematical expression, a good option is to use asymptotic methods to obtain an estimate of that term. For example, the nth prime number is approximately nlognwhen nis very big. The authors of [4] also also point out that using generating functions some properties of a succession such as unimodality or convexity can be proven. Another advantage of using generating functions is that some identities as, for example,

j=0nnj2=2nnn=0,1,2,E16

are easy to obtain. Finally, the authors of [4] pointed out that by using generating function, the relationship between problems that have similar generating functions can be discovered.

As was mentioned in the last paragraph, sometimes it is hard to obtain mathematically closed formulas when using generating functions, and in that case, a good alternative is to the use asymptotic formulas. The mathematical tools used for this purpose are part of the field known as analytic combinatorics, and a good reference of this topic is [3]. The main objective of analytic combinatorics is to estimate with a high level of precision the properties of large structured combinatorial configurations by the use of mathematical analysis tools [3].Under this approach, we begin with an exact enumerative description of the combinatorial structure using the generating functions. This description is considered as an algebraic object. The next step is to take the generating function as an analytical object which is a mapping from the complex plane to itself. The singularities found in such a mapping allow to obtain the coefficients of the function in its asymptotic form, resulting in an excellent estimate on the count of the sequences. With this purpose, the authors of [3] classify the analytic combinatorics in the next three topics:

  1. Symbolic methods that establish systematically relations of discrete mathematics constructions and operations on generating functions that encode counting sequences

  2. Complex asymptotics that allow for extracting asymptotic counting information from the generating functions by the mapping to the complex plane mentioned above

  3. Random structures concerning the probabilistic properties accomplished by large random structures

A large material concerning the subject of complex asymptotic analysis is addressed in [5]. A highly recommended text to consult because it covers the applications of the combinatorial tools enumerative to the analysis of algorithms is [6]. In this chapter, there will be a particular interest in the application of generating functions tool for the enumeration of graphs that have some given properties.

Let us start with the definition of a graph. A graph G=VEis a structure with a set of vertices V=v1v2vpwhose size V=pit is called the order of G and a set of unordered pairs of adjacent vertices, called edges, E=vi1vj1vi2vj2viqvjqif G is undirected or a set of ordered pairs of adjacent vertices E=vi1vj1vi2vj2viqvjq, if G is a directed graph, whose edge set size is E=q, that has no loops and that has no loops multiple edges. A graph G with p vertices and q edges is called a pqgraph. In a labeled graph of order p, each vertex has a label that is an integer from 1 to p. Typical questions such as how many graphs can be constructed with nvertices, how many trees with nvertices can be obtained, and how many of these trees are binary can be answered using the generating functions, and a mathematically closed formula can be obtained. In the case that a closed mathematical formula is very hard to be obtained, an accurate asymptotic estimation formula can be a good option.

There are two commonly used generating functions: the first is the ordinary generating functions (OFG) and the other is the exponential generating functions (EGF).

An ordinary generating function is a mathematical function defined by the following expression:

ax=k=0akxk,E17

where the coefficients are elements of the succession of numbers a0,a1,a2,. The ordinary generating functions are used for enumeration problems where the order of the objects is not important. An exponential generating function is a mathematical function defined by the following expression:

bx=k=0bkxkk!,E18

where the coefficients are elements of the succession of numbers b0,b1,b2,. The exponential generating function are used for enumeration problems where the order of the objects matter. Graphs, words, trees, or integer partitions are some of the kinds of objects with which combinatorics deals. Combinatorics deals with discrete objects as, for example, graphs, words, trees, and integer partitions. Counting such objects is one of the most interesting tasks. Enumeration of graphs that have some structural property is the main purpose of the present chapter.

The great mathematician George Pólya made huge contributions to the field of graph enumeration graphs. He obtained closed mathematical expressions for the enumeration of graphs with a given number of vertices and edges for many graph counting problems using group theory [7]. Pólya’s formulas greatly facilitated the enumeration of rooted graphs, connected graphs, etc. The enumeration of number of triangulations of certain plane polygons was one of the first problems of enumeration that attracted the attention of the great mathematician Leonhard Euler [8] in the eighteenth century. Some years later, Kirchhoff in [9] discovered a method for enumerating spanning trees in a connected graph. After that, Arthur Cayley obtained a closed mathematical formula that enumerates labeled trees, rooted trees, and ordinary trees in [10]. The Cayley discovery will be covered with more detail in Section 4. The brilliant and unknown mathematician John Howard Redfield [11] discovered many enumeration formulas anticipating some of Pólya’s contributions.

Some enumeration problems of objects that are not graphs (automata, Boolean functions, or chemical isomers) can be solved by cleverly transforming them to graphs. The generating functions are the tool used for enumerating graphs. There are two types of graphs associated with combinatorial graph enumeration problems:

  1. Labeled graph problems

  2. Unlabeled graph problems

Some enumeration problems of labeled graphs are normally addressed by applying the exponential generating functions tool. The enumeration problems of unlabeled graphs are normally addressed by applying the ordinary generating functions but require the application of Pólya’s theorem.

One of the first problems of enumerating labeled graphs that may arise is that of how many graphs with pvertices and qedges can be obtained.

To solve this enumeration problem, let Gpxbe the polynomial or ordinary generating function whose coefficient of the term xkrepresents the number of labeled graphs with pvertices and kedges. If Vis the set of vertices of cardinality p, there are q=p2pairs of these vertices. In every vertex set V, each pair is adjacent or not adjacent. The number of labeled graphs with kedges is therefore qk=p2k. Thus, the ordinary generating function Gpxfor labeled graphs with pvertices is given by

Gpx=k=0mmkxk=1+xm,E19

where m=p2. Then, the number of labeled graphs with pvertices is Gp1; so we have:

Gp=2m=2p2.E20

For example, if we want to know how many labeled graphs with p=3vertices can be obtained, we apply Formula (20), and we get:

G3=232=23!2!1!=23=8.E21

If we want to know how many labeled graphs with p=4vertices and exactly q=5edges exist, before expression (19), we use the coefficient of the term x5

x5Gpx=x5k=066kxk=65=6!5!1!=6.E22

A question that arises naturally when working with labeled graphs is in how many ways can this be constructed from a certain number of vertices and edges. In order to give a possible answer, the number of symmetries or automorphisms must be taken into account. It is said that there is isomorphism between two graphs G and G1 if there is a one-to-one map A:VGVG1between them that preserve adjacency. When G1=G, then the mapping Ais called automorphism of G. The set of all the automorphisms of G, represented by ΓG, is called the group of G. The elements of ΓGare permutations over V. Let sG=ΓGbe the order of the group or number of symmetries of G. Therefore, the number of ways in which a graph Gof order pcan be labeled is

lG=p!sG.E23

Another example of graph enumeration problem is to count the number of differently labeled connected graphs. The notion of path of length nis defined as a sequence of vertices v0v1vnwhere the edges vivi+1for i=0,nthat belong to the path are distinct. It is said that a graph is connected if for any pair of vertices there is a path between them. To obtain the formula that counts all the connected graphs Cpof order p, it will be necessary to make use of the concept of subgraph. It is said that a His a subgraph of a graph Gif VHVGand EHEG. A subgraph that is maximally connected is called component. A rooted graph is a graph that has a distinguished vertex called root. When there exists an injective mapping f:VH1VH2between two rooted graphs H1and H2that preserves the adjacency among vertices as well as the roots, it is said that the two rooted graphs are isomorphic. Let us make the assumption that akfor k=1,2,3,represents the number of ways in which we can label all graphs of order that accomplish the property Paand whose exponential generating function is

ax=k=1akxkk!.E24

Let us also assume that bkfor k=1,2,3,is the number of ways of labeling all graphs of order that accomplish the property Pband whose exponential generating function is

bx=k=1bkxkk!.E25

If we make the product of series (24) and (25), the coefficients of xkk!in axbxis the number of ordered pairs G1G2of two disjoint graphs, where G1meets the property Pa, G2fulfills the property Pb, kis the number of vertices in G1G2, and the labels from 1 to k have been distributed over G1G2. If Cxis the exponential generating function for labeled connected graphs

Cx=k=1Ckxkk!,E26

then CxCxbecomes the generating function that counts all the ordered pairs of connected graphs with labels. If you divide by 2, equation (26) that is, we divide it by 2, we get the generating function for labeled graphs that have exactly two components.

By applying this operation n times, the coefficient of xkk!that corresponds to the number of labeled graphs of order k is obtained with exact n components

Gx=n=1Cnxn!.E27

From (27), we obtain the following relation

1+Gx=eCx.E28

Riordan in [12] obtained the relation Cp=Jp2, where Jpxenumerates the trees by inversions, and then deduced

Cp=k=1p1p2k12k1CkCpk.E29

From (29), it should be noted that if the exponential generating function for the graph class is known in advance, then the exponential generating function for the class of graphs will be the logarithm of the first series, just as in (28). It should also be mentioned that another equivalent recurrence function can be obtained for the enumeration of the connected graphs that have order tags p (p. 7 in [13]) and that can be expressed mathematically as

Cp=2p21pk=1p1kpk2pk2Ck.E30

From (30), the following MATLAB code can be implemented for calculating the number of connected graphs Cp of orders going from p=1to p=20.

function y = CuentaGrafConnEtiq( p )

% recurrence satisfied by the number of connected graphs

% Harary Graph Enumeration pag. 7

% C_p= 2ˆ{combinations(p,2)}-1/p* \sum_{k=1}ˆ{p-1} k*

% combinations(p,k)*2ˆ{combinations(p-k,2)}*C_{k}

C(1:p)=0;

C(1,1)=1;

for k=2:p

acum=0;

for j=1:k

  acum = acum + j * combinaciones(k,j) * CuentaGrafEtiq(k-j) * C(1,j);

end

C(1,k) = CuentaGrafEtiq(k)-(1/k)*acum;

end

y=C(1,p);

sprintf(‘end function z=combinaciones(n,k) z= factorial(n)/(factorial(k)*factorial(n-k));

end

function z=combinaciones(n,k)

  z= factorial(n)/(factorial(k)*factorial(n-k));

end

%% calling the function from the matlab prompt for the calculation of the

%% evaluation from graphs of order 1 to 20

>> for i=1:20

  R(1,i)=CuentaGrafConnEtiq( i );

end

The calculations obtained by the execution of MATLAB code are shown in Table 1.

pCp
11
21
34
438
5728
626,704
71,866,256
8251,548,592
966,296,291,072
1034,496,488,594,816
1135,641,657,548,953,344
127.335460×1019
133.012722×1023
142.471649×1027
154.052768×1031
161.328579×1036
178.708969×1040
181.41641×1046
192.992930×1051
201.569216×1057

Table 1.

Order 1–20.

From the results of 1, it can be observed that the number of possible connected graphs Cp grows very fast in terms of the number p of vertices. It should be mentioned that (29) and (30) are recurrence relations instead of a closed formula. The recurrences (29) or (30) can be used for the calculation of Cp with a computer program. The generating functions can be used to solve recurrences and obtain a closed mathematical expression for the nth term of the succession associated with the recurrence. It can happen that calculation of the solution of some recurrences becomes very hard to be solved and in the worst cannot be solved at all. An alternative method for obtaining an approximate value for big values of p is to recur to the application of methods used in analytic combinatorics and calculate accurate approximations of the pth coefficient of the generating function. The generating functions algebraic structure allows to reflect the structure of combinatorial classes. The analytic combinatorics method consists in examining the generating functions from the point of view of the mathematical analysis by giving not only real value values to its variables but also values in the complex plane. When complex values are assigned to the variables of the generating functions, the function is converted in a geometric transformation of the complex plane. This kind of geometrical mapping is said to be regular (holomorphic) near the origin of the complex plane. When we move away from the origin of the complex plane, some singularities appear that are related with the absence of smoothness of the function and give a lot of information about the function coefficients and their asymptotic growth. It can happen that elementary real analysis is enough for estimating asymptotically enumerative successions. If this is not the case, the generating functions are still explicit, but its form does not allow the easy calculation of the coefficients of the series. The complex plane analysis however is a good option for asymptotic estimation of these coefficients. In order to give an example of the use of the notion of singularities, let us take the ordinary generating function of the Catalan numbers

fx=12114x.E31

Eq. (31) expresses in a compact way the power series of the form

1y1/2=112y18y2.E32

The generating function (31) coefficients can be explicitly expressed as

fn=xnfx=1n2n2n1.E33

Using the Stirling formula, we can get the asymptotic approximation of (33) that is expressed as

fnlimn4nπn3.E34

If the generating function is used as an analytic object, the approximation (34) can be obtained.

In order to do it, we substitute in the power series expansion of the generating function f(x) any real or complex value ρfwhose modulus is small enough, for example, ρf=4. The graph that we get by the use of (31) is smooth and differentiable in the real plane and tends to the limit 12as x14, but, if we calculate its derivative, we obtain the following function

fx=1114x,E35

and it can be noticed that the derivative (35) becomes infinite in ρf=14. The singularities will correspond to those points where the graph is not smooth.

It should be pointed out that that the region where function (31) is still being continuous can be extended. Let us take for example the value x=1

f1=1215.E36

We can evaluate in the same manner (31) giving to x values in the complex plane whose modulus is less than the radius of convergence of the series defined by (31) and realize that the orthogonal and regular grid in it transforms the real plane in a grid on the complex plane that preserves the angles of the curves of the grid. This property corresponds to the complex differentiability property, which also is equivalent to the property of analyticity. Concerning the asymptotic behavior of the coefficients fn of the generating function, it should be observed that it has a general asymptotic pattern composed by an exponential growth factor Anand a subexponential factor θn.

For the case of the expression (34) A=4and θn14πn31, the exponential growth factor can be put in relation with the radius of convergence of the series by A=1ρfthat is the singularity that can be observed along the positive real axis of the complex plane that normally corresponds to the pole of the generating function, and the subexponential part θn=On32arises from the singularity of the square root type. This asymptotic behavior can be compactly expressed as

xnfx=Anθn.E37

The exponential growth part of (37) is known as first principle of coefficient asymptotics and the subexponential growth part as second principle of coefficient asymptotics. By recalling to the results that can be found in the field complex variable theory, more general generating functions can be obtained. One of those results is the Cauchy residue theorem that relates global properties of a meromorphic function (its integral along closed curves) to purely local characteristics at the residues poles. An important application of the Cauchy residue theorem concerns a coefficient of analytic functions. This is stated in the following theorem [3]:

Theorem 1.5 (Cauchy’s coefficient formula). Let fzbe analytic in a region containing 0, and let λbe a simple loop around 0 that is positively oriented. Then, the coefficient znfzadmits the integral representation:

fnznfz=12λfzdzzn+1.E38

For more details about analytic combinatorics, we recommend to consult [3] as well as [5].

4. Enumeration of trees

A graph is a structure composed by a set of vertices V=v1v1vnand a set of pairs of connected vertices E=e1e2emcalled edges where EV×Vand each edge ekEis composed as pair of vertices ek=vivj. A tree is a special type of graph that do not have cycles. A tree have no loops or edges that connect a vertex with himself. The subject of combinatorial graph enumeration has been the center of interest of many mathematicians a long time ago. The enumeration of total possible labeled trees with n nodes being nn2was one of first results obtained by Cayley in [10]. Cayley’s formula for enumerating trees is one of the simple and elegant mathematical results in enumeration of graphs. He detected that from n+1vertices, the number of possible trees that can be built is equal to n+1n1. Cayley [10] gives an example for the case of four vertices 4=n+1then n=3, and the total number of possible trees calculated using his formula gives 42=16. In this same publication, Cayley gives another example having n+1=6vertices (he used the term knots in his publication) with labels a,b,c,d,e,fand related the concatenation of vertices given by the edges for obtaining sequences of labels representing a given tree. For instance, if the tree is a chain of vertices connected by edges starting with the vertex a and ending with the vertex f and having as connecting edges ab,bc,cd,de,ef, the corresponding label sequence is abcdefas shown in Figure 1. As another example of sequence of vertex labels, if the root of the tree is αand it is connected directly with the other five vertices, then the connecting edges will be ab,ac,ad,ae,af, and the corresponding sequence of vertex labels will be in that case a5bcdefas shown in Figure 2. As can be noticed, the exponent of a is 5 that represents the number of occurrences of this label in the set of connecting edges.

Figure 1.

Example of tree of one branch.

Figure 2.

Example of tree with more branches.

After that Cayley states the theorem for this particular case as follows:

Theorem 1.6 The total number of trees Tn+1that can be built with n+1=6vertices can be calculated as follows

Tn+1=a+b+c+d+e+f4abcdef=64=1296E39

This calculation relates the sum of the products of the coefficients of the multinomial a+b+c+d+e+f4with the number of terms of its corresponding type. Each term obtained by multiplying abcdefwith the vertex label inside a+b+c+d+e+f4corresponds to different trees.

At the end of [10], Cayley generalizes his theorem by recalling a result obtained by C.W. Borchardt in [14] that relates some particular kind of determinants that represent spanning trees and whose product represents the branches of those spanning trees. Given that the number of terms of these determinants is n+1n1, Cayley can conclude that the number of spanning trees is the same. Since these first results, many other methods have been proposed for obtaining the same result. One way to enumerate a collection of objects is to find a bijection between a set of objects whose enumeration is known and the set of objects that we want to enumerate. This was the method used by Prüfer in [15] for enumerating the set of possible spanning trees with n vertices. The set whose number was known beforehand was a sequence of length n2of numbers from 1 to n. For this end the autor of article [15] encoded the trees as Prüfer sequences. In [16] Moon generalized the result derived by Clarke in [17] by induction on d the degree, making induction on n, and the number of vertices and obtains a new enumeration method for n-labeled k trees.

5. Enumeration and generating functions

The field of combinatorial enumeration has aroused enormous interest among mathematicians who have worked in the area of discrete mathematics during the last decades [18, 19, 20, 21]. Combinatorial enumerative technique developed by these brilliant researchers have allowed us to count words, permutations, partitions, sequences, and graphs. As was mentioned in Section 3, the mathematical tool frequently used for this purpose is the generating functions or formal power series.

The generating functions allow to connect discrete mathematics and continuous analysis in a very special way with complex variable theory. The typical situation that someone faces when trying to solve an enumeration problem is that you want to know the mathematically closed form that has the nth term of a given sequence of numbers a0,a1,a2,For some sequences, we can do by inspection. For example, if the numerical sequence 1,3,5,7,9,, it is easy to see that it is a sequence of odd numbers whose nth element is an=2n1.

A more complicated sequence is the set of prime numbers 2,3,5,7,11,13,17,19,, whose an is the nth prime number. A closed mathematical formula for nth prime number is not known, and it seems impossible to obtain in general.

In many cases it is very hard to get a simple formula just by inspection. However it can be very useful to use the generating functions whose coefficients are the elements of that sequence transforming it as follows:

i=0aixi.E40

Eq. (40) defines an ordinary generating function. As mentioned in Section 3, since they are infinite polynomials, they can be algebraically manipulated easily.

In this chapter, the main interest will be the application of the generating functions tool as well as the analytic asymptotic methods for the enumeration of graphs accomplishing some given properties. Many questions about the number of graphs that have some specified property can be answered by the use of generating functions. Some typical questions about the number of graphs that fulfill a given property are, for example: How many different graphs can I build with n vertices? How many different connected graphs with n vertices exist? How many binary trees can be constructed with n vertices? [18, 19], etc. For some of these questions, the application of generating functions allows us to easily obtain a simple formula. For some other questions, the answer is an asymptotic estimation formula. The most commonly used generating functions are the ordinary generating functions and the exponential generating functions. The generating functions are the tool used for enumerating graphs. From the point of view of the generating functions, there are two types of graph enumerating problems:

  1. Labeled graph problems

  2. Unlabeled graph problems

The labeled graph problems can be easily solved with the direct application of the exponential generating functions. The case of the unlabeled enumeration problems can be solved by using ordinary generating functions but require the use of more combinatorial theory and the application of Pólya’s theorem.

6. Enumerating regular graphs

As we mentioned in Section 6, some enumerating problems can be solved easily using generating tools for obtaining a closed formula. Some other problems are more hard to deal with for obtaining a closed mathematical expression, but we can resort in such a case to the asymptotic approximation of the coefficients of the power series [22, 23, 24, 25]. It was also mentioned in Section 6 that there are some graph enumerating problems where the nodes are labeled, and in such a case the use of the exponential generating functions is well adapted for these kinds of problems. The other case of graph enumerating problems is when we are dealing with graphs whose nodes do not have an assigned label. Then, we can resort in such case to Pólya’s enumerating method [7, 13], and the best choice is to use ordinary generating functions. It should also be mentioned that the edges of the graphs to be enumerated can be directed or undirected.

One of the seminal articles of enumerating graphs is [26], where a fundamental theorem was proven in the theory of random graphs on n unlabeled nodes and with a given number q of edges.

In [26], the authors obtained a necessary and sufficient condition for relating asymptotically the number of unlabeled graphs with n nodes and q edges with the number of labeled graphs with n nodes and q edges. Let Tnq be the number of different graphs with n nodes and q edges, Fnq the corresponding to number of labeled graphs, N=nn12the possible edges, and Fnq=Nq=N!q!Nq!. The result obtained in [26] can be stated as the following theorem:

Theorem 1.7 The necessary and sufficient conditions that

TnqFnqn!E41

as nis that

minqNq/nlogn/2.E42

The formal result expressed in Theorem 1.7 for unlabeled graphs is a starting point on the enumeration of regular graphs because it allows for enumerating those unlabeled graphs that have some number of edges. In fact, the author of [26] proved that if a graph with E=Enedges, where n is the number of vertices or order of such a graph, has no isolated vertices or two vertices of degree n − 1, then the number of unlabeled graphs of order n and number of edges Edivided by the number unlabeled graphs is asymptotic to n!.

Another interesting article on asymptotic enumeration of labeled graphs having a given degree sequence was [27]. The authors of [27] obtained their asymptotic result for n×nsymmetric matrices subject to the following constraints:

  1. Each row sum is specified and bounded.

  2. The entries are bounded.

  3. A specified sparse set of entries must be zero.

The authors of [27] mentioned that their results can be interpreted in terms of incidence matrices for labeled graphs. The results of [27] can be stated as follows. Let Mnzbe the set of all n×nsymmetric 01matrices with at most zzeroes in each row, ra vector over d=01d, and GMrtthe number of n×nsymmetric matrices gijover t=01tsuch that

  1. gij=0if mij=0.

  2. jgij=ri.

Theorem 1.8 For given d,tand z,

GMrtTfδeεabri!.E43

Uniformly, for Mrn=1Mnz×0dnas f, where f=iri,ε=1ift=1and+1ift>1, for a=iri2f2+mijri2f,b=mij=0,i<jrirj+iri2f,δ=mij=0riand Tfδbeing the number of involutions on [1, f] such that no element in some specified set of size δis fixed.

Three years later, the article [28] appeared giving a different approach of [27] allowing for obtaining a more general asymptotic formula without reference to an exact formula. The asymptotic result obtained by Bela Bollobás in [28] for enumerating labeled regular graphs is proven by a probabilistic method. This result can be stated as follows. Let Δand n be natural numbers such that Δn=2mis even and Δ2logn12, where n is the number of vertices and m is the number of edges of the graph G. Then, as n, the number of labeled Δ-regular graphs on n vertices is asymptotic to

eλλ22m!m!2mΔ!m,E44

where λ=Δ12.

The authors of [27] affirm that the asymptotic Formula (44) holds not only for Δconstant but also for Δgrowing slowly as nand summarized this in the following theorem.

Theorem 1.9 Let d1d2dnbe natural numbers with i=1ndi=2meven. Suppose Δ=d12logn121and mmaxεΔn1+εnfor some ε>0. Then, the number Ldof labeled graphs with degree sequence d=di1nsatisfies

Ldeλλ22mm2mi=1ndi!,E45

where λ=12mi=1ndi2.

In the next year, the author on [27] extended this result to the case of unlabeled graphs in [29].The result of Theorem 1.9 extended for the case of unlabeled graphs can be summarized in the following theorem.

Theorem 1.10 If Δ3and LΔ=eλλ22m!m!2mΔ!m, then

UΔLΔn!eΔ2142m!2mm!Δ!nn!,E46

where m=Δn2.

For the details of the proof of Theorems 1. 9 and 1.10, see [28, 29], respectively.

7. Example of proof of a result on control using combinatorial enumeration

In [30] I used the combinatorial enumeration methods and probability for showing the applicability of the selection node criteria in a virus spreading control problem in complex networks. The main purpose of this section is to illustrate how the enumerative combinatorics in combination with probability theory can be used for demonstrating mathematically a result in an application field. We can mention that the case of homogeneity in the behavior of the nodes and their interaction cannot be discarded given what has been observed in the reaction of the agents in the context of social networks is that they try to minimize the conflict. Many successful models can, for example [30, 31, 32, 33], base their predicting effectiveness on the homogeneity of the behavior of the nodes and their interaction. By the other side, in [30] we have obtained a criteria for selecting the nodes to be controlled, but such criteria fail if we have homogeneity in the behavior of the nodes and, at the same time, the topology of the network is regular. Then, what we want to do here is to justify the applicability of node selection criteria, keeping the homogeneity of the nodes and trying to compare the number of regular graphs with n vertices with the total of graphs that can be constructed with n vertices. For this end, based on the results on combinatorial graph enumeration mentioned on Theorems 1.9 and 1.10, we can state our main result as follows. First of all, we suppose that our graph is labeled, G=VEis r-regular with r3constant and rn=2m, where n=Vcorresponds to the number of vertices and m=Ecorresponds to the number of edges. Let Lr the number of labeled regular graphs of degree r whose asymptotic value is [28]

Lrer2142m!2mm!r!n.E47

Let Gn be the number of all possible graphs with n vertices whose value is

Gn=2n2.E48

Theorem 1.11 If r3and nr=2m, then

limnLrGn=0.E49

Proof of Theorem 1.11. If nr=2mand r is constant of value c1, then we can deduce that m=r2n=c12n, and this implies that m=Onso let us say that m=c2n; then,

limnLrGn=limnec12142c2n!c1!n2c2nc2n!2n2E50
=limnec1214c1!n2c2n!2c2nc2n!2nn12,E51

applying the approximation Stirling formula n!2πnnen

c1!n=2πc1c1ec1nE52

then

=limnec12142πc1c1ec1n2c2n!2c2nc2n!2nn12E53

simplifying

=limn12πc1nc1c1nec12+4c1n+142c2n!2c2nc2n!2nn12E54

applying the approximation Stirling formula

2c2n!=2π2c2n2c2ne2c2nE55

and

c2n!=2πc2nc2nec2nE56

we get

=limn12πc1nc1c1nec12+4c1n+142π2c2n2c2ne2c2n2c2n2πc2nc2nec2n2nn12,E57

simplifying

=limn22πc1nc1c1nec12+4c1n+1/4c2nec2n2nn12E58

given that r3, for which we assumed that r is a constant c1, and that nr=2m, then we have that c1=2c2, and replacing that, in (58), we can express it in terms of c1, which is the regular degree r assumed as fixed; then, we get

limn22πc1nc1c1nec12+4c1n+1/4c1n/2ec1n/22nn12,E59

and, replacing c1 by r in (59), we get

limn22πrnrrner2+4rn+1/4rn/2ern/22nn12.E60

Therefore, if the degree r is constant, the limnLrGn=0.

Now, our main result can be stated as a consequence of Theorem 1.11.

Theorem 1.12 If we assume that all graphs are uniformly distributed and that the nodes have homogeneous behavior, then the criteria for selecting nodes to be controlled are almost always applicable.

Proof of Theorem 1.11. As a consequence of Theorem 11, we know that the probability that a regular graph appears tends to zero as n. Then, the mentioned criteria are almost always applicable.

8. Conclusions

In the present chapter, some problems of combinatorial graph enumeration as well as some useful techniques for obtaining a closed mathematical expression were addressed. When it is not possible to obtain a closed expression, asymptotic estimations of the kind used in analytic combinatorics can be used. In Section 10 the use of these techniques for proving a result in the field of virus spreading control was illustrated [31, 32, 33, 34].

This allowed to explore the application of combinatorial techniques to control problems in networks and thus verify the goodness of said methods for network analysis and the control of virus propagation in them. This still needs to be studied by applying the combinatorial methods discussed above, if there are any other types of topologies that prevent the application of the selection criteria of nodes to be controlled under the hypothesis of behavior of partially heterogeneous nodes, that is, if in the network we have subsets of nodes with the same behavioral parameters. The selecting node criteria described in [30] are based on the combination of the parameter values of the selected nodes as well as their degrees. In many recent publications [35, 36, 37, 38, 39, 40, 41, 42], interesting and elaborated methods for detecting the influencer nodes in complex networks have been proposed that I will try to apply in combination with the mentioned criteria in the future in order to reduce the number of nodes to be controlled.

Download

chapter PDF

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Carlos Rodríguez Lucatero (August 31st 2019). Combinatorial Enumeration of Graphs [Online First], IntechOpen, DOI: 10.5772/intechopen.88805. Available from:

chapter statistics

32total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us