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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 20221. 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 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1195687271 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Dissociation number” revision 1195687271 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001195687271 · captured 1705265866.0 · version history

Cite this page as: encyclopegia.org, “Dissociation number”, snapshot enwiki-001195687271. https://encyclopegia.org/a/dissociation-number