×

Decycling Cartesian products of two cycles. (English) Zbl 1096.05030

Summary: The decycling number \(\nabla(G)\) of a graph \(G\) is the smallest number of vertices which can be removed from \(G\) so that the resultant graph contains no cycles. In this paper, we study the decycling number for the family of graphs consisting of the Cartesian product of two cycles. We completely solve the problem of determining the decycling number of \(C_m \square C_n\) for all \(m\) and \(n\). Moreover, we find a vertex set \(T\) that yields a maximum induced tree in \(C_m\square C_n\).

MSC:

05C38 Paths and cycles
05C05 Trees
94C15 Applications of graph theory to circuits and networks
Full Text: DOI