错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cycle Isolation of Graphs with Small Girth

  • Gang Zhang,
  • Baoyindureng Wu

摘要

Let G be a graph. A subset \(D \subseteq V(G)\) D V ( G ) is a decycling set of G if \(G-D\) G - D contains no cycle. A subset \(D \subseteq V(G)\) D V ( G ) is a cycle isolating set of G if \(G-N[D]\) G - N [ D ] contains no cycle. The decycling number and cycle isolation number of G, denoted by \(\phi (G)\) ϕ ( G ) and \(\iota _c(G)\) ι 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}\) ϕ ( G ) 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\) C g , then \(\iota _c(G) \le \frac{m+1}{g+2}\) ι c ( G ) m + 1 g + 2 , and they presented a proof for the initial case \(g=3\) 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.