The Decycling Number of Cubic Planar Graphs

Abstract

Bau and Beineke [2] asked the following questions: 1 Which cubic graphs G of order 2n have decycling number ? 1 Which cubic planar graphs G of order 2n have decycling number ? We answered the first question in [10]. In this paper we prove that if is the class of all connected cubic planar graphs of order 2n and , then there exist integers a n and b n such that there exists a graph with φ(G) = c if and only if c is an integer satisfying a n ≤ c ≤ b n . We also find all corresponding integers a n and b n . In addition, we prove that if is the class of all connected cubic planar graphs of order 2n with decycling number and , then there exists a sequence of switchings σ 1, σ 2, ..., σ t such that for every i=1, 2, ..., t-1, and . © 2007 Springer-Verlag Berlin Heidelberg.