THE RECURRENCE RELATIONS FOR THE NUMBER OF THE NONISOMORPHIC (n,m)-GRAPHS - Stegantseva, P. G.; Artemenko, A. O. (Computer Science and Applied Mathematics, 2021)
The problem connected with the enumeration and the calculation of the graphs includes the problems connected with the enumeration and calculation of the labeled graphs and the unlabeled graphs. The second one is considered to be more difficult. There are also the problems connected with the enumeration of the graphs of certain type. For example, the enumeration of the labeled ordinary nondirected graphs, the labeled ordinary directed graphs, the labeled connected nondirected graphs, the labeled trees, the unlabeled trees and the others. Redfield – Polya theorem, which follows from Burnside lemma, is the classical result on the enumeration of the graphs. The graph G with n vertices and m edges is called n,m -graph. Two n,m -graphs are called the isomorphic ones if the bijection exists between the sets of the vertices, which preserves their adjacency. The article deals with the problem connected with the calculation of T n,m nonisomorphic ordinary n,m -graphs using the concept of the vector of the degrees of the graph. The vector of the degrees of the graph is its noncomplete invariant with respect to the isomorphisms. The sequences of the numbers T n,m for n ≤ 20 can be found in the Online Encyclopedia of Integer Sequences under the number A008406. The properties of this table have been studied in the present article. One of these properties expresses the relation between the quantity of all pairwise nonisomorphic graphs with m edges and the number of vertices which differ by 1. It has been shown that if the collection of all pairwise nonisomorphic n,m -graphs contains the graph with the vector of the degrees (1,1,…,1), then n = 2m . The recurrence relations, which give an opportunity to find certain numbers of the nonisomorphic graphs with n vertices and m edges under n > 20 which are not given in the table, have been obtained. The concept of the reduction of the vector of the degrees of the graph (P-transformation) has been introduced in order to prove the recurrence relations. The relation between the collections of the pairwise nonisomorphic graphs with the same number of the edges and the different number of the vertices has been studied with the help of P-transformation. The well-known Harary formula for the finding of the number of the nonisomorphic simple graphs has been used in order to confirm the correctness of the obtained results.