1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Decycling Number of a Planar Graph Covered By K4-Subgraphs

Published Online: 27 May 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 15 Jul 2020
Accepted: 10 Apr 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let G be a planar graph of n vertices. The paper shows that the decycling number of G is at most n12 {{n - 1} \over 2} if G has not any K4-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 n2 {n \over 2} if and only if G is covered by K4-subgraphs. In addition, the decycling number of G covered by octahedron-subgraphs or icosahedron-subgraphs is studied.

Keywords

MSC 2010

[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. Search in Google Scholar

[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 Search in Google Scholar

[3] J.A. Bondy and U.S.R.Murty, Graph Theory (Springer, 2008).10.1007/978-1-84628-970-5 Search in Google Scholar

[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. Search in Google Scholar

[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-610.1016/0095-8956(86)90028-6 Search in Google Scholar

[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.10.1007/978-1-4757-3023-4_4 Search in Google Scholar

[7] K. Hosono, Induced forests in trees and outerplanar graphs, Proc. Fac. Sci. Tokai Univ. 25 (1990) 27–29. Search in Google Scholar

[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_910.1007/978-1-4684-2001-2_9 Search in Google Scholar

[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-N10.1016/0012-365X(94)00268-N Search in Google Scholar

[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.2221810.1002/jgt.22218 Search in Google Scholar

[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/S089548010444016X10.1137/S089548010444016X Search in Google Scholar

[12] N. Punnim, The decycling number of regular graphs, Thai J. Math. 4 (2006) 145–161. Search in Google Scholar

[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.01110.1016/j.disc.2017.07.011 Search in Google Scholar

[14] A.T. White, Graphs, Groups and Surfaces (North-Holland, 1973). Search in Google Scholar

[15] H. Whitney, Two-isomorphic graphs, Trans. Amer. Math. Soc. 34 (1932) 339–362. https://doi.org/10.1090/S0002-9947-1932-1501641-210.1090/S0002-9947-1932-1501641-2 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo