Properties of vertex cover obstructions |
| |
Authors: | Michael J Dinneen Rongwei Lai |
| |
Institution: | Department of Computer Science, University of Auckland, Auckland, New Zealand |
| |
Abstract: | 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 O(k-VERTEX COVER) and call it the set of obstructions. Our main result is to give a tight vertex bound of O(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 C2k+1. We also find two iterative methods to generate graphs in O((k+1)-VERTEX COVER) from any graph in O(k-VERTEX COVER). |
| |
Keywords: | Vertex cover Obstructions Forbidden graphs |
本文献已被 ScienceDirect 等数据库收录! |