# zbMATH — the first resource for mathematics

The decycling number and maximum genus of cubic graphs. (English) Zbl 1393.05166
Summary: Let $$\nabla(G)$$ and $$\gamma_M(G)$$ denote the minimum size of a decycling set and maximum genus of a graph $$G$$, respectively. For a connected cubic graph $$G$$ of order $$n$$, it is shown that $$\nabla(G)+\gamma_M(G)= \frac{n}{2}+1$$. Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set $$S$$ in a $$k$$-regular graph $$G$$ is $$|S| = \frac{1}{k-1}\{\beta (G)+ c + m^\prime_s - 1 \}$$, where $$c$$ and $$m_s^\prime$$ are the number of components of $$G-S$$ and the number of edges in $$G[S]$$, respectively. Therefore, $$S$$ is minimum if and only if $$c+m^\prime_S -1$$ is minimum. As an application, this leads to a lower bound $$\nabla(G) \geq \lceil \frac{\beta (G)}{k-1} \rceil$$ for $$\nabla(G)$$ of a $$k$$-regular graph $$G$$. In many cases this bound may be sharp.

##### MSC:
 05C38 Paths and cycles
Full Text: