Cycle isolation of graphs with small girth (Q6131294)

Let \(G=(V,E)\) be a graph of order \(n\), size \(m\) and girth \(g\). A subset \(D\) of \(V\) is a decycling set of \(G\) if \(G-D\) contains no cycle and is called a cycle isolating set of \(G\) if \(G-N[D]\) contains no cycle. The decycling number \(\phi(G)\) and the cycle isolation number \(i_c(G)\) are respectively the minimum cardinalities of a decycling set and cycle isolating set of \(G\) respectively. If girth of \(G\) is at least \(g\), then \(\phi(G)\leq \frac{m}{g}\) and \(i_c(G)\leq \frac{m+1}{g+2}\) are two conjectures which remain unsolved. This paper deals with the conjecture \(i_c(G)\leq \frac{m+1}{g+2}\). The validity of this conjecture for \(g=3\) is proved in an earlier paper. In this paper, it has been proved that the conjecture is valid for graphs with girths at least 4, 5, and 6, and the extremal graphs are characterized. The conjecture remains open for \(g\geq 7\).