| Meno: | Radoslav |
|---|---|
| Priezvisko: | Petráni |
| Názov: | Distance dominating circuits in cubic graphs |
| Vedúci: | doc. RNDr. Robert Luko»ka, PhD. |
| Rok: | 2026 |
| Kµúčové slová: | dominating circuit, dominating cycle, distance k-dominating cycle, cubic graphs, edge connectivity, cyclic connectivity |
| Abstrakt: | A cycle C is a distance k-dominating cycle of graph G, if for every vertex v of G, there exists a path from v to C of length at most k. The cycle distance of a graph G, is the smallest k ∈ N, such that G has a distance k-dominating cycle. This concept is an aproximation of Hamiltonicity, as a graph with cycle distance of 0 is Hamiltonian. We establish upper bounds for the cycle distance of graphs of given edge connectivity, depending on the order of the graph. By construction of classes of graphs with small amounts of vertices for their cycle distance we prove the tightness of these bounds or try to approach them. We also show a satisfiability approach to the problem of determining the cycle distance, by constructing SAT formulas in CNF for the existance of distance k-dominating cycles. |
Súbory diplomovej práce:
| master_thesis_Petráni.pdf |
Súbory prezentácie na obhajobe: