# zbMATH — the first resource for mathematics

The decycling number of cubic graphs. (English) Zbl 1117.05022
Akiyama, Jin (ed.) et al., Combinatorial geometry and graph theory. Indonesia-Japan joint conference, IJCCGGT 2003, Bandung, Indonesia, September 13–16, 2003. Revised selected papers. Berlin: Springer (ISBN 3-540-24401-8/pbk). Lecture Notes in Computer Science 3330, 141-145 (2005).
Summary: For a graph $$G$$, a subset $$S \subseteq V(G)$$, is said to be a decycling set of $$G$$ if if $$G \setminus S$$ is acyclic. The cardinality of smallest decycling set of $$G$$ is called the decycling number of $$G$$ and it is denoted by $$\phi(G)$$. S. Bau and L. W. Beineke [Australas. J. Comb. 25, 285–298 (2002; Zbl 0994.05079)] posed the following problems: Which cubic graphs $$G$$ with $$|G| = 2n$$ satisfy $$\phi(G) = \lceil \frac{n+1}2 \rceil$$? In this paper, we give an answer to this problem.
For the entire collection see [Zbl 1063.05001].

##### MSC:
 05C07 Vertex degrees 05C35 Extremal problems in graph theory
##### Keywords:
degree sequence; decycling number; cubic graph
Full Text: