 Hitting subgraphs in P4-tidy graphsBoštjan Brešar, Tim Kos, Rastislav Krivoš-Belluš and Gabriel Semanišin Applied Mathematics and Computation, 2019, vol. 352, issue C, 211-219 Abstract: Vertex cover number, which is one of the most basic graph invariants, can be viewed as the smallest number of vertices that hit (or that belong to) every subgraph K2 in a graph G. In this paper, we consider the next two smallest cases of connected graphs, which are the path P3 and the cycle C3; the problem is to minimize the set of vertices that hit every subgraph H in G, where H is one of the two graphs. We focus on computational aspects of these two variations of the vertex cover number. We show that both problems are NP-complete even in the class of graphs that have no induced cycles of length t, where t∈{4,…,8} (in fact, in the P3-hitting case, the problem is NP-complete in even smaller family of graphs, where also triangles are forbidden). On the positive side, we prove a complementary result that in graphs with no induced P4 (the so-called cographs) both problems become linear. Moreover, we consider a generalization of cographs — P4-tidy graphs, for which we establish an efficient algorithm for both problems. Keywords: Hitting set; Decycling number; k-path vertex cover; P4-tidy graph; Quasi-spider (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:352:y:2019:i:c:p:211-219 DOI: 10.1016/j.amc.2019.01.074 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.