pith. sign in

arxiv: 1812.09305 · v1 · pith:XHHEPL5Nnew · submitted 2018-12-21 · 🧮 math.CO

Isolation of cycles

classification 🧮 math.CO
keywords graphiotaboundcaroclosedconnectedconsequentlycontains
0
0 comments X
read the original abstract

For any graph $G$, let $\iota_{\rm c}(G)$ denote the size of a smallest set $D$ of vertices of $G$ such that the graph obtained from $G$ by deleting the closed neighbourhood of $D$ contains no cycle. We prove that if $G$ is a connected $n$-vertex graph that is not a triangle, then $\iota_{\rm c}(G) \leq n/4$. We also show that the bound is sharp. Consequently, we solve a problem of Caro and Hansberg.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.