Publication: The Decycling Number of Cubic Planar Graphs
2
0
Issued Date
2007
Resource Type
File Type
application/pdf
ISSN
3029743
Other identifier(s)
2-s2.0-49949093746
Rights Holder(s)
มหาวิทยาลัยศรีนครินทรวิโรฒ
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4381 LNCS, (2007), p.149-161
Suggested Citation
Punnim N. The Decycling Number of Cubic Planar Graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 4381 LNCS, (2007), p.149-161. doi:10.1007/978-3-540-70666-3_16 Retrieved from: https://hdl.handle.net/20.500.14740/4242
Author(s)
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.