The minimum feedback vertex set for kronecker product of graphs

Abstract

For a graph G of order n and S ⊂ V(G), if G \ S is a acyclic graph, then S is said to be a feedback vertex set. The aim is to minimize the cardinality of 5, this problem is called the minimum feedback vertex set. In this paper we study the minimum feedback vertex set for the Kronecker product of graphs, where the Kronecker product of two graphs G and H denoted by G ⊗ H is a graph with vertex set V(G ⊗ H) = V(G) × V(H) and edge set E(G ⊗ H) = {{(u,x), (v,y)} : {u,v} ε E(G) and {x,y} ε E(H)}.