Abstract:

Let $G = (V, E)$ be a simple graph and $F$ be a subset of $V$. If the subgraph induced by the subset $V-F$ does not contain cycles, then $F$ is called a feedback set of $G$. The smallest value of the numbers of vertices in feedback sets is called the feedback number of $G$, denoted by $f(G)$, that is, $f(G)=\min\{|F| : F$ is a feedback set of $G\}$. Caragiannis et al. obtained the upper bounds of the feedback number of 2-dimensional meshes. In this paper, we improve the upper bounds.

Key words: 2-dimensional meshes, feedback vertex set, feedback number, acyclic subgraph