Decycling sets in certain cartesian product graphs with one factor complete.
Bert L. Hartnell, Carol Whitehead · 2008
A decycling set in a graph G is a set D of vertices such that G − D is acyclic. The decycling number of G, φ(G), is the cardinality of a smallest decycling set in G. We obtain sharp bounds on the value of the cartesian product φ(G Kr) when r ≥ 3 and prove that when G belongs to one of several well-known families of graphs, including bipartite graphs and graphs of maximum degree 3, then φ(G K3) = n+φ(G) and φ(G Kr) = n(r− 2) for r ≥ 4, where n is the order of G. We prove also that every cubic graph G 6= K4 contains an independent decycling set.