Structural and algorithmic properties of maximal dissociating sets in graphs

A subset of the vertex set of a graph is called dissociating if the degrees of the vertices of the subgraph generated by this subset do not exceed $1$. A dissociating set is maximal if it is not contained in any dissociating set with a greater number of vertices. Estimates for the greatest (smallest) number of vertices in a maximal dissociating set of a graph are proposed. It is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for quasichordal bipartite graphs. In addition, it is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for chordal bipartite graphs, bipartite graphs with the greatest degree of a vertex equal to 3, planar graphs with large girth, and for classes of graphs characterized by finite lists of forbidden generated biconnected subgraphs. A linear algorithm for solving the latter problem in the class of trees is proposed.