Dissociation number

Examples for the definition of the dissociation number

In the mathematical discipline of graph theory, a subset of vertices in a graph G is called dissociation if it induces a subgraph with maximum degree 1. The number of vertices in a maximum cardinality dissociation set in G is called the dissociation number of G, denoted by diss(G). The problem of computing diss(G) (dissociation number problem) was firstly studied by Yannakakis. The problem is NP-hard even in the class of bipartite and planar graphs.

An algorithm for computing a 4/3-approximation of the dissociation number in bipartite graphs was published in 2022.

The dissociation number is a special case of the more general Maximum k-dependent Set Problem for $k=1$. The problem asks for the size of a largest subset $S$ of the vertices of a graph $G$, so that the induced subgraph $G[S]$ has maximum degree $k$.

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal