On the Complexity of Dissociation Set Problems in Graphs

What is it about?

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with vertex degree at most 1. A dissociation set D is maximal if no other dissociation set contains D. The complexity of finding a dissociation set of maximum size in line graphs and finding a maximal dissociation set of minimum size in general graphs is considered.

Featured Image