DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

D.-J. Ma

Dengju Ma

School of Sciences, Nantong University

email: ma-dj@163.com

M.-Y. Ma

Mingyuan Ma

Department of Mathematics, East China Normal
University

email: ming623@163.com

H. Ren

Han Ren

email: hren@math.ecnu.edu.cn

Title:

The decycling number of a planar graph covered by $K_4$-subgraphs

PDF

Source:

Discussiones Mathematicae Graph Theory 44(2) (2024) 459-473

Received: 2020-07-15 , Revised: 2022-04-10 , Accepted: 2022-04-10 , Available online: 2022-05-04 , https://doi.org/10.7151/dmgt.2455

Abstract:

Let $G$ be a planar graph of $n$ vertices. The paper shows that the decycling number of $G$ is at most $\frac{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 $\frac{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.

Keywords:

decycling number, planar graph, $K_4$-minor

References:

  1. M.O. Albertson and D.M Berman, The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XVII (1976) 51–69.
  2. L.W. Beineke and R.C. Vandell, Decycling graphs, J. Graph Theory 25 (1997) 59–77.
    https://doi.org/10.1002/(SICI)1097-0118(199705)25:1<59::AID-JGT4>3.0.CO;2-H
  3. J.A. Bondy and U.S.R.Murty, Graph Theory (Springer, 2008).
  4. O.V. Borodin, A proof of Grüngaum's conjecture on the acyclic $5$-colorability of planar graphs, Dokl. Akad. Nauk SSSR 231 (1976) 18–20, in Russian.
  5. P. Erdős, M. Saks and V. Sós, Maximum induced trees in graphs, J. Combin. Theory Ser. B 41 (1986) 61–79.
    https://doi.org/10.1016/0095-8956(86)90028-6
  6. P. Festa, P.M. Pardalos and M.G.C. Reseude, Feedback set problem, in: Handbook of Combinatorial Optimization, Supplement Vol. A, (Kluwer, Dordrecht 1999) 209–258.
  7. K. Hosono, Induced forests in trees and outerplanar graphs, Proc. Fac. Sci. Tokai Univ. 25 (1990) 27–29.
  8. R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller, J.W. Thatcher, J.D. Bohlinger (Ed(s)), (The IBM Research Symposia Series Springer, Boston, MA 1972) 85–103.
    https://doi.org/10.1007/978-1-4684-2001-2_9
  9. J.P. Liu and C. Zhao, A new bound on the feedback vertex sets in cubic graphs, Discrete Math. 184 (1996) 119–131.
    https://doi.org/10.1016/0012-365X(94)00268-N
  10. S.D. Long and H. Ren, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018) 375–384.
    https://doi.org/10.1002/jgt.22218
  11. D.A. Pike and Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005) 651–663.
    https://doi.org/10.1137/S089548010444016X
  12. N. Punnim, The decycling number of regular graphs, Thai J. Math. 4 (2006) 145–161.
  13. H. Ren, C. Yang and T.-X. Zhao, A new formula for the decycling number of regular graphs, Discrete Math. 340 (2017) 3020–3031.
    https://doi.org/10.1016/j.disc.2017.07.011
  14. A.T. White, Graphs, Groups and Surfaces (North-Holland, 1973).
  15. H. Whitney, Two-isomorphic graphs, Trans. Amer. Math. Soc. 34 (1932) 339–362.
    https://doi.org/10.1090/S0002-9947-1932-1501641-2
Close