Source author record

Barbora Candráková

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.OC

Catalog footprint

Research overview

3works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Cubic TSP - a 1.3-approximation

We prove that every simple bridgeless cubic graph with n >= 8 vertices has a travelling salesman tour of length at most 1.3n - 2, which can be constructed in polynomial time.

preprint2015arXiv

Short cycle covers on cubic graphs using chosen 2-factor

We show that every bridgeless cubic graph $G$ with $m$ edges has a cycle cover of length at most $1.6 m$ . Moreover, if $G$ does not contain any intersecting circuits of length $5$ , then $G$ has a cycle cover of length $212/135 \cdot m \approx 1.570 m$ and if $G$ contains no $5$ -circuits, then it has a cycle cover of length at most $14/9 \cdot m \approx 1.556 m$ . To prove our results, we show that each $2$ -edge-connected cubic graph $G$ on $n$ vertices has a $2$ -factor containing at most $n/10+f(G)$ circuits of length $5$ , where the value of $f(G)$ only depends on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each $3$ -edge-connected cubic graph on $n$ vertices has a $2$ -factor containing at most $n/9$ circuits of length $5$ and each $4$ -edge-connected cubic graph on $n$ vertices has a $2$ -factor containing at most $n/10$ circuits of length $5$ .

preprint2014arXiv

Avoiding 5-circuits in a 2-factor of cubic graphs

We show that every bridgeless cubic graph $G$ on $n$ vertices other than the Petersen graph has a 2-factor with at most $2(n-2)/15$ circuits of length $5$ . An infinite family of graphs attains this bound. We also show that $G$ has a 2-factor with at most $n/5.8\overline{3}$ odd circuits. This improves the previously known bound of $n/5.41$ [Lukoťka, Máčajová, Mazák, Škoviera: Small snarks with large oddness, arXiv:1212.3641 [cs.DM] ].

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.