| Meno: | Eliąka
|
|---|
| Priezvisko: | Krajčíová
|
|---|
| Názov: | Finding the longest induced cycles in cubic graphs
|
|---|
| Vedúci: | Mgr. Matúą Matok
|
|---|
| Rok: | 2025
|
|---|
| Kµúčové slová: | inducedcycle, cubic graph, backtracking, pruning heuristics, computational study
|
|---|
| Abstrakt: | We address the problem of finding the length of the longest induced cycle in cubic
graphs, a specialized case of the broader induced-cycles problem. Leveraging known
bounds—that any cubic graph contains an induced 2-regular subgraph on at most
3n/4
vertices—we develop a backtracking algorithm that incrementally builds chord-free
paths and closes them into cycles. Key pruning ideas—forcing single-choice extensions,
discarding vertices once their best cycles are known, and abandoning paths that cannot
surpass the current best—shrink the search dramatically. On graphs up to 28 vertices,
our approach runs in milliseconds versus minutes for naïve subset-enumeration.
Experiments on various cubic graph families confirm correctness and illustrate extremal
examples with very short longest induced cycles. Our results combine new structural
insights with a practical tool for exploring cycle extremality in low-degree graphs.
|
|---|