On Complexity of Total Vertex Cover on Subcubic Graphs

Abstract

A total vertex cover is a vertex cover whose induced subgraph consists of a set of connected components, each of which contains at least two vertices. A t-total vertex cover is a total vertex cover where each component of its induced subgraph contains at least t vertices. The total vertex cover (TVC) problem and the t-total vertex cover (t-TVC) problem ask for the corresponding cover set with minimum cardinality, respectively. In this paper, we first show that the t-TVC problem is NP-complete for connected subcubic grid graphs of arbitrarily large girth. Next, we show that the t-TVC problem is NP-complete for 3-connected cubic planar graphs. Moreover, we show that the t-TVC problem is APX-complete for connected subcubic graphs of arbitrarily large girth.