How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm

DOI10.46298/DMTCS.10189arXiv2210.05080MaRDI QIDQ6131778FDOQ6131778

Authors: Juan Carlos García-Altamirano, M. Olsen 

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: In 2020 Bang-Jensen et. al. generalized the Haj'os 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'os constructions (directed Haj'os join and identifying non-adjacent vertices), determining the Haj'os constructions to obtain the digraph is a complex problem. In particular, Bang-Jensen et al. posed the problem of determining the Haj'os operations to construct the symmetric 5-cycle from the complete symmetric digraph of order 3 using only Haj'os 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'os 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'os operations to construct the symmetric cycle of order 5.

Full work available at URL: https://arxiv.org/abs/2210.05080

Recommendations

• Hajós-type constructions and neighborhood complexes
• An analogue of Hajós' theorem for the circular chromatic number. II
• scientific article; zbMATH DE number 4002120
• The graph constructions ofHaj�s and Ore
• scientific article; zbMATH DE number 1487668

zbMATH Keywords

dichromatic numberdirected Hajós joinrank-based genetic operators

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131778)