Paired dominating set

colored red In graph theory, a paired dominating set of a graph G = (V, E) is a dominating set S of vertices such that the induced subgraph G[S] contains at least one perfect matching.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

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.

colored red In graph theory, a paired dominating set of a graph G = (V, E) is a dominating set S of vertices such that the induced subgraph G[S] contains at least one perfect matching. The concept was introduced by Teresa W. Haynes and Peter J. Slater in 1998.

The paired domination number, denoted \gamma_p(G) , is the minimum cardinality of a paired dominating set of G . The concept models a situation in which guards are placed at vertices of a graph to dominate (protect) all vertices, with the additional constraint that each guard is assigned another adjacent guard as a backup. This is equivalent to finding a set M of independent edges (a matching) whose endpoints form a dominating set.

Haynes and Slater characterized the triples (a, b, c) of positive integers with a \leq b \leq c for which there exists a graph G satisfying \gamma(G) = a , \gamma_t(G) = b , and \gamma_p(G) = c . Because the endpoints of any maximal matching form a paired dominating set, the paired domination number is bounded above by twice the size of any maximal matching of the graph: \gamma_p(G) \leq 2\,\nu(G) where \nu(G) denotes the size of a maximum matching. Define the family \mathcal{F} as the set of graphs obtainable from three nonempty sets of parallel edges, \{u_r v_r : r = 1, \ldots, k\} , \{w_s x_s : s = 1, \ldots, l\} , and \{y_t z_t : t = 1, \ldots, m\} , by connecting each pair of vertices (v_r, w_s) , (x_s, y_t) , and (z_t, u_r) with a path of length two (introducing a new vertex of degree two for each such pair).

The original k + l + m edges are called the associated matching of the resulting graph. When k = l = m = 1 , the resulting graph is the cycle graph C_9 . A connected, leafless graph of girth at least seven has a maximal matching whose endpoints form a minimum paired dominating set if and only if it belongs to the family \mathcal{F} .

A consequence of this characterization is that any such graph containing an 8-cycle must contain a specific 18-vertex graph, denoted P_{18} , as an induced subgraph; this occurs precisely when at least two of the parameters k, l, m are at least 2.

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

Provenance

snapshot enwiki-001335024242 · captured 2026-01-26 · ledger · version history

Cite this page as: encyclopegia.org, “Paired dominating set”, snapshot enwiki-001335024242. https://encyclopegia.org/a/paired-dominating-set

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.