THE DECYCLING NUMBER OF A PLANAR GRAPH COVERED BY K4-SUBGRAPHS

作者：Ma, Dengju^*; Ma, Mingyuan; Ren, Han

来源：Discussiones Mathematicae Graph Theory, 2022.

DOI：10.7151/dmgt.2455

• decycling number
• planar graph
• K-4-minor

Let G be a planar graph of n vertices. The paper shows that the decycling number of G is at most n-1/2 if G has not any K-4-minor. If the maximum degree of G is at most four and G is not 4-regular, the paper proves that the decycling number of G is n/2 if and only if G is covered by K-4-subgraphs. In addition, the decycling number of G covered by octahedron-subgraphs or icosahedron-subgraphs is studied.

• 单位
  南通大学