| Meno: | Alex |
|---|---|
| Priezvisko: | Diko |
| Názov: | Even cycle decompositions in graphs |
| Vedúci: | doc. RNDr. Ján Mazák, PhD. |
| Rok: | 2026 |
| Kµúčové slová: | even cycle decomposition, edge coloring, 4-regular graphs, 6-regular graphs, 8-regular graphs |
| Abstrakt: | An even cycle decomposition of a graph is a partition of its edge set into cycles of even length. The even cycle decomposition index of a graph is the minimum number of colors needed over all its even cycle decompositions, where the cycles in each decomposition are colored so that cycles meeting at a vertex receive different colors. We develop SAT and backtracking algorithms for determining even cycle decomposition index and compare their performance in practice. Using these algorithms, we determine the even cycle decomposition index for all 4-, 6-, and 8-regular graphs up to a certain order. Furthermore, we analyze the results, prove some of them theoretically, and formulate new conjectures. In addition, we prove that the circulant graphs $C_{2n+1}(1,2)$ and $C_{2n+1}(1,3)$ have even cycle decomposition index 3, while the graphs $C_{2n+1}(1,2,3,4)$ have index 5. Finally, we construct infinite families of maximally connected 4-, 6-, and 8-regular graphs of even order with even cycle decomposition index 3, 4, and 5, respectively. |
Súbory bakalárskej práce:
| bakalarka.pdf |
| ba-graph.zip |
Súbory prezentácie na obhajobe: