Robert Lukoťka

collaborators

2 papers

cs.DM2017

Simple cubic graphs with no short traveling salesman tour

Robert Lukoťka, Ján Mazák

Let $t s p (G)$ denote the length of a shortest travelling salesman tour in a graph $G$ . We prove that for any $ε > 0$ , there exists a simple $2$ -connected planar cubic graph…

math.CO2017

Perfect matchings in highly cyclically connected regular graphs

Robert Lukoťka, Edita Rollová

A leaf matching operation on a graph consists of removing a vertex of degree~ $1$ together with its neighbour from the graph. For $k \geq 0$ , let $G$ be a $d$ -regular cyclically $(d-…