Properties of vertex cover obstructions Original Research Article

We study properties of the sets of minimal forbidden minors for the families of graphs having a vertex cover of size at most k. We denote this set by image(k-VERTEX COVER) and call it the set of obstructions. Our main result is to give a tight vertex bound of image(k-VERTEX COVER), and then confirm a conjecture made by Liu Xiong that there is a unique connected obstruction with maximum number of vertices for k-VERTEX COVER and this graph is image. We also find two iterative methods to generate graphs in image(image-VERTEX COVER) from any graph in image(k-VERTEX COVER).