@inproceedings{1a1d8b8be002401abee8e9e51968761b,
title = "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.",
author = "Poon, {Sheung Hung} and Wang, {Wei Lin}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",
year = "2017",
doi = "10.1007/978-3-319-55911-7_37",
language = "English",
isbn = "9783319559100",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "515--528",
editor = "Gerhard Jager and Silvia Steila and T.V. Gopal",
booktitle = "Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings",
address = "Germany",
}