تقرير
A procedure to obtain symmetric cycles of any odd length using directed Haj\'os constructions
العنوان: | A procedure to obtain symmetric cycles of any odd length using directed Haj\'os constructions |
---|---|
المؤلفون: | García-Altamirano, Juan Carlos, Olsen, Mika, Cervantes-Ojeda, Jorge |
سنة النشر: | 2023 |
المجموعة: | Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics, 05C20, 05C15 |
الوصف: | The dichromatic number of a digraph $D$ is the minimum number of colors of a vertex coloring of $D$ such that $D$ has no monochromatic cycles. The Haj\'os join were recently extended to digraphs (using the dichromatic number) by J. Bang-Jensen et. al. and Haj\'os (directed) operations is a tool to obtain r-(di)chromatic (di)graphs. J. Bang-Jensen et. al. posed in 2020 the problem of how to obtain the symmetric cycle of length 5 from symmetric cycles of length 3. We recently solved this problem by applying a genetic algorithm. In this article, a procedure is presented to construct any odd symmetric cycle by applying directed Haj\'os operations to symmetric cycles of length 3, thus, generalizing the known construction of the symmetric cycle of length 5. In addition, this procedure is analyzed to determine its computational complexity. Comment: 9 pages, 4 figures. arXiv admin note: text overlap with arXiv:2210.05080 |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2301.07181 |
رقم الأكسشن: | edsarx.2301.07181 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!