Abstract
Let G be a graph. A subset \(D \subseteq V(G)\) is a decycling set of G if \(G-D\) contains no cycle. A subset \(D \subseteq V(G)\) is a cycle isolating set of G if \(G-N[D]\) contains no cycle. The decycling number and cycle isolation number of G, denoted by \(\phi (G)\) and \(\iota _c(G)\), are the minimum cardinalities of a decycling set and a cycle isolating set of G, respectively. Dross, Montassier and Pinlou (Discrete Appl Math 214:99–107, 2016) conjectured that if G is a planar graph of size m and girth at least g, then \(\phi (G) \le \frac{m}{g}\). So far, this conjecture remains open. Recently, the authors proposed an analogous conjecture that if G is a connected graph of size m and girth at least g that is different from \(C_g\), then \(\iota _c(G) \le \frac{m+1}{g+2}\), and they presented a proof for the initial case \(g=3\). In this paper, we further prove that for the cases of girth at least 4, 5 and 6, this conjecture is true. The extremal graphs of results above are characterized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. J. Graph Theory 38, 113–123 (2001)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 244. Springer, New York (2008)
Borg, P.: Isolation of cycles. Graphs Combin. 36, 631–637 (2020)
Borg, P., Fenech, K., Kaemawichanurat, P.: Isolation of \(k\)-cliques. Discrete Math. 343, 111879 (2020)
Borg, P., Fenech, K., Kaemawichanurat, P.: Isolation of \(k\)-cliques II. Discrete Math. 345, 112641 (2022)
Borg, P., Kaemawichanurat, P.: Partial domination of maximal outerplanar graphs. Discrete Appl. Math. 283, 306–314 (2020)
Borg, P., Kaemawichanurat, P.: Extensions of the art gallery theorem. Ann. Combin. 27, 31–50 (2023)
Caro, Y., Hansberg, A.: Partial domination—the isolation number of a graph. Filomat 31, 3925–3944 (2017)
Chen, J., Xu, S.-J.: \(P_5\)-isolation in graphs. Discrete Appl. Math. 340, 331–349 (2023)
Cui, Q., Zhang, J.: A sharp upper bound on the cycle isolation number of graphs. Graphs Combin. 39, 117 (2023)
Dross, F., Montassier, M., Pinlou, A.: A lower bound on the order of the largest induced forest in planar graphs with high girth. Discrete Appl. Math. 214, 99–107 (2016)
Dross, F., Montassier, M., Pinlou, A.: Large induced forests in planar graphs with girth 4. Discrete Appl. Math. 254, 96–106 (2019)
Favaron, O., Kaemawichanurat, P.: Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph. Discrete Appl. Math. 289, 93–97 (2021)
Hua, H., Hua, X.: Admissible property of graphs in terms of independence number. Bull. Malays. Math. Sci. Soc. 45, 2123–2135 (2022)
Kelly, T., Liu, C.-H.: Minimum size of feedback vertex sets of planar graphs of girth at least five. Eur. J. Combin. 61, 138–150 (2017)
Kelly, T., Liu, C.-H.: Size of the largest induced forest in subcubic graphs of girth at least four and five. J. Graph Theory 89, 457–478 (2018)
Le, H.: A better bound on the largest induced forests in triangle-free planar graphs. Graphs Combin. 34, 1217–1246 (2018)
Shi, L., Xu, H.: Large induced forests in graphs. J. Graph Theory 85, 759–779 (2017)
Tokunaga, S., Jiarasuksakun, T., Kaemawichanurat, P.: Isolation number of maximal outerplanar graphs. Discrete Appl. Math. 267, 215–218 (2019)
Wang, Y., Xie, Q., Yu, X.: Induced forests in bipartite planar graphs. J. Combin. 8, 93–166 (2017)
Yan, J.: Isolation of the diamond graph. Bull. Malays. Math. Sci. Soc. 45, 1169–1181 (2022)
Yu, H., Wu, B.: Admissible property of graphs in terms of radius. Graphs Combin. 38, 6 (2022)
Zhang, G., Wu, B.: \(K_{1,2}\)-isolation in graphs. Discrete Appl. Math. 304, 365–374 (2021)
Zhang, G., Wu, B.: Isolation of cycles and trees in graphs. J. Xinjiang Univ. (Nat. Sci. Ed. Chin. Eng.) 39, 169–175 (2022)
Zhang, G., Wu, B.: A note on the cycle isolation number of graphs. Bull. Malays. Math. Sci. Soc. 47, 57 (2024)
Acknowledgements
The authors would like to thank the two anonymous referees for their careful reading and valuable comments.
Funding
The work is supported by the open project of Key Laboratory in Xinjiang Uygur Autonomous Region of China (2023D04026) and by National Natural Science Foundation of China (No. 12061073).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, G., Wu, B. Cycle Isolation of Graphs with Small Girth. Graphs and Combinatorics 40, 38 (2024). https://doi.org/10.1007/s00373-024-02768-7
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-024-02768-7