A generalization of the pentomino exclusion problem: dislocation of graphs (Q864131): Difference between revisions

A pattern formed by the connection of a specified number of equal-sized squares along common edges is called a polyomino, and if a polyomino is made up of five squares then it is called a pentomino. The concept of polyomino is due to Golomb who also proposed the following pentomino exclusion problem: Find the minimum number, denoted by \(P(k,n)\), of unit squares to be placed on a \((k\times n)\) chessboard so as to exclude all pentominoes. In this paper, this problem is solved for the \((5\times n)\) grid and some upper and lower bounds are provided for the \((k\times n)\) grid for all \(k\) and \(n\). The generalization of the problem to graphs, called the \(\Delta\)-dislocation problem, amounts to finding the minimum number of vertices to be removed from a graph so that all the remaining connected components have cardinality at most \(\Delta\). The algorithmic aspects of the \(\Delta\)-dislocation problem is also discussed, and it is shown that the problem of calculating the value of \(P(k,n)\) has a solution with a running time, with \(k\) fixed, being polynomial in \(n\).