RELATION OF HAMILTONIAN AND DENSITY OF THE GRAPH ADJACENCY RELATION

Smirnov Danila Antonovich

In the process of considering pairs of different characteristics of graphs, a search was made for a possible correlation between any one pair of such characteristics. As a result, a conjecture about pancyclic graphs was formed, which is the main conclusion of the experiments. The calculations were carried out using the parallelization of the calculation process, all source codes were written in the object-oriented language C ++ and executed under the control of a Unix-like Debian open source community system. In order for the calculations not to become too time-consuming, dynamic programming techniques were used to search for the Hamiltonian cycle, however, even with this optimization, the graphs generated by the Nauty package are considered only up to 12 vertices, since it becomes too laborious to carry out calculations on a larger number of vertices even with optimizations.

Keywords:graph, cycle, pancyclicity, dynamic programming, parallel programming.