How to construct the symmetric cycle of length 5 using Hajós construction with an adapted Rank Genetic Algorithm
This solves a specific graph theory problem for researchers in digraphs and combinatorial optimization, but it is incremental as it applies an existing algorithm to a new domain.
The paper tackled the problem of determining Hajós constructions to build a symmetric 5-cycle from a complete symmetric digraph of order 3, as posed by Bang-Jensen et al., and achieved a sequence of only 16 Hajós operations using an adapted rank-based genetic algorithm.
In 2020 Bang-Jensen et. al. generalized the Hajós join of two graphs to the class of digraphs and generalized several results for vertex colorings in digraphs. Although, as a consequence of these results, a digraph can be obtained by Hajós constructions (directed Hajós join and identifying non-adjacent vertices), determining the Hajós constructions to obtain the digraph is a complex problem. In particular, Bang-Jensen et al. posed the problem of determining the Hajós operations to construct the symmetric 5-cycle from the complete symmetric digraph of order 3 using only Hajós constructions. We successfully adapted a rank-based genetic algorithm to solve this problem by the introduction of innovative recombination and mutation operators from graph theory. The Hajós Join became the recombination operator and the identification of independent vertices became the mutation operator. In this way, we were able to obtain a sequence of only 16 Hajós operations to construct the symmetric cycle of order 5.