Research On High Performance Algorithms For Constructing The Graphs Without Hexagons

As an important branch of mathematics,graph theory is widely used in computer science,economic finance,natural social science and other fields.In the field of graph theory,the study of extremal graph is of great value,especially for the research of general extremal graph problems.It mainly studies the maximum number of edges of the graphs that do not contain the forbidden subgraph family?={H₁,H₂,…,H_m}.The research results of this problem can provide theoretical support for many problems in other fields of graph theory.In this paper,we study the high performance algorithms for constructing the graphs without hexagon.The research contents and results are as follows:?1?By using the graph symmetry,an algorithm of constructing graph based on basic graphs?CGBG?is proposed.When constructing a graph with a large number of vertices without hexagon,if the algorithm is based on the critical graphs,its construction process will include two processes of adding and deleting edges,which results in a long running time.The algorithm CGBG continuously expands the edges of the basic graph by adding points and edges to the basic graph,and updates the basic graph to construct a graph without hexagon.Hence,the proposed algorithm does not include the process of deleting the edges.Moreover,by making full use of the graph symmetry during the extension process,the executing time of the algorithm CGBG is shortened effectively.Finally,we employ this algorithm to construct the graphs without hexagon when the number of vertices are from 29 to 50,and give the lower bounds of ex?n;{C₆}?of the extremal graph.?2?In order to construct the extremal graphs without hexagon with a small number of vertices,an algorithm for constructing graphs based on Spark?CGS?is proposed.The existing algorithm based on critical graphs can generate a large number of intermediate graphs,which results in a great quantity of disk read and write operations,thus increasing the calculation time of the algorithm.Therefore,the algorithm CGS is designed to solve this problem in this paper.By using the characteristics of Spark completely based on memory computing and the capacity of cluster for increasing the memory,the algorithm CGS can reduce the number of disk read and write operations to improve the efficiency of the algorithm.Besides,the algorithm CGS makes full use of the algorithm for determining the isomorphism of the graphs to reduce the number of intermediate graphs,which can effectively reduce the executing time of the algorithm.The experimental results show that the speed-up ratio and the execution efficiency of the algorithm achieve2.1486 and 71.62% respectively.