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].

05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI