Juan Carlos García-Altamirano ; Mika Olsen ; Jorge Cervantes-Ojeda - How to construct the symmetric cycle of length 5 using Hajós construction with an adapted Rank Genetic Algorithm

dmtcs:10189 - Discrete Mathematics & Theoretical Computer Science, March 1, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.10189
How to construct the symmetric cycle of length 5 using Hajós construction with an adapted Rank Genetic AlgorithmArticle

Authors: Juan Carlos García-Altamirano ; Mika Olsen ; Jorge Cervantes-Ojeda

    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.


    Volume: vol. 25:1
    Section: Discrete Algorithms
    Published on: March 1, 2023
    Accepted on: February 3, 2023
    Submitted on: October 21, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Artificial Intelligence,05C20, 05C15, 68T20, 68W50

    Consultation statistics

    This page has been seen 772 times.
    This article's PDF has been downloaded 572 times.