×

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
PDF BibTeX XML Cite
Full Text: DOI