Cycle isolation of graphs with small girth
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\).
- \( K_{1 , 2}\)-isolation in graphs
- \( P_5\)-isolation in graphs
- A better bound on the largest induced forests in triangle-free planar graph
- A lower bound on the order of the largest induced forest in planar graphs with high girth
- A note on the cycle isolation number of graphs
- A sharp upper bound on the cycle isolation number of graphs
- Admissible property of graphs in terms of independence number
- Admissible property of graphs in terms of radius
- Extensions of the Art Gallery Theorem
- Graph theory
- Induced forests in bipartite planar graphs
- Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph
- Isolation number of maximal outerplanar graphs
- Isolation of \(k\)-cliques
- Isolation of \(k\)-cliques. II
- Isolation of cycles
- Isolation of the diamond graph
- Large induced forests in graphs
- Large induced forests in planar graphs with girth 4
- Large induced forests in sparse graphs
- Minimum size of feedback vertex sets of planar graphs of girth at least five
- Partial domination -- the isolation number of a graph
- Partial domination of maximal outerplanar graphs
- Size of the largest induced forest in subcubic graphs of girth at least four and five
- A note on the cycle isolation number of graphs
- \(k\)-isolation in graphs
- On the cycle isolation number of triangle-free graphs
- Cycle isolation in graphs
- Total isolation of k-cliques in a graph
- A characterization of graphs with maximum k-clique isolation number
- A characterization of graphs with maximum cycle isolation number
- Proof of a conjecture on isolation of cycles in graphs
- Isolation of non-triangle cycles in graphs
- Graphs with total isolation number equal to half the order
- Bounds on the game isolation number and exact values for paths and cycles
This page was built for publication: Cycle isolation of graphs with small girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131294)
