On a Countable Family of Boundary Graph Classes for the Dominating Set Problem

Abstract: A hereditary class is a set of simple graphs closed under deletion of vertices; every suchclass is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then theclass is said to be finitely defined. The concept of a boundary class is a useful tool for the analysisof the computational complexity of graph problems in the family of finitely defined classes. Thedominating set problem for a given graph is to determine whether it has a subset of vertices of agiven size such that every vertex outside the subset has at least one neighbor in the subset.Previously, exactly four boundary classes were known for this problem (if). The present paper considers a countable set of concrete classes of graphsand proves that each its element is a boundary class for the dominating set problem (if). We also prove the-completeness of this problem for graphs that contain neither an induced6-path nor an induced 4-clique, which means that the set of known boundary classes for thedominating set problem is not complete (if). © Pleiades Publishing, Ltd. 2023.