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.
Researcher profile
Barbora Candráková
Barbora Candráková contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
3topics
1close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
3 published item(s)
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$.
0 citations0 reviewsNo code linkedOpen access
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] ].
0 citations0 reviewsNo code linkedOpen access