Book chapter
Оценка числа графов в некоторых подклассах двудольных графов
In book
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite graphs, matchings, Petri nets, planar graphs, transport nets). Some algorithms often used in practice on graphs are given. It is considered classical combinatorial configurations and their generating functions, recurrent sequences. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty of National Research University Higher School of Economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some constants c1 and c2. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. Only the properties with speeds up to the Bell number are well studied and well behaved. To better understand the behavior of factorial properties with faster speeds we introduce a structural tool called locally bounded coverings and show that a variety of graph properties can be described by means of this tool.
For a graph property X, let Xn be the set of graphs with the vertex set {1, . . . , n} that satisfy the property X. A property X is called factorial if X is hereditary (i. e. closed under taking induced subgraphs) and nc1n ≤ X ≤ nc2n for some positive constants c1 and c2. A graph G is a quasi-line if for every vertex v, the set of neighbors of v can be expressed as a union of two cliques. In the present paper we identify almost all factorial subclasses of quasi-line graphs defined by one forbidden induced subgraph. We use these new results to prove that the class Free(K1,3,W4) is factorial, which improves on a result of Lozin, Mayhill and Zamaraev [8].