Connected Dominating Set¶
A vertex subset of an undirected graph that dominates every excluded vertex while inducing a connected subgraph on its selected vertices.
Core Idea¶
A connected dominating set (CDS) of a finite undirected graph \(G=(V,E)\) is a nonempty vertex subset \(D\) whose every excluded vertex has a neighbor in \(D\) and whose selected vertices induce a connected subgraph \(G[D]\). Direct coverage of outsiders and paths inside the selected subset are separate requirements. A CDS need not be smallest: the connected domination number \(\gamma_c(G)\) is the separate minimum size over all eligible sets.[^ref-c15991172f95]
Scope of Application¶
In graph theory, a CDS can be related to a spanning tree: for a connected graph with at least three vertices, the tree's nonleaf vertices form a CDS, and a CDS can be extended to a tree with its excluded vertices among the leaves. Thus the optimum values, not arbitrary individual sets and trees, obey \(\gamma_c(G)+L(G)=|V|\), where \(L(G)\) is the maximum leaf count.[^ref-c15991172f95]
In an undirected unit-disk model of a wireless ad hoc network, selected radios can form a virtual backbone while each unselected radio has a one-hop modeled link into it. Wan, Alzoubi and Frieder study distributed construction and the appeal of a relatively thin backbone; their model does not prove that all real radio links satisfy the same assumptions.[^ref-fd89078d4b3f]
Clarity¶
To test a proposed \(D\), check each outsider's direct adjacency to \(D\), then check paths among selected vertices using only other selected vertices. On the five-vertex path, \(\{2,4\}\) dominates but is disconnected; \(\{2,3,4\}\) passes both tests. On the five-vertex star, the center alone passes them. Claiming either example is minimum requires an additional lower-bound argument, not just the membership test.[^ref-c15991172f95]
Manages Complexity¶
The two tests compress a potentially large network into an internally linked covering subset: outsiders have local contact with the core, and the core can connect through its own members. Smaller cores may be desirable, but finding or constructing them has separate computational and communication costs. A larger established set remains a CDS when it meets both tests.[^ref-fd89078d4b3f]
Abstract Reasoning¶
Treat CDS membership as a conjunction: domination of outsiders and connectivity of \(G[D]\). Failure of either is decisive. In particular, full-graph connectivity cannot substitute for induced connectivity of the selected vertices. The spanning-tree correspondence can transform a minimum-CDS question into a maximum-leaf question when \(|V|\geq3\), but it does not make every CDS minimum.[^ref-c15991172f95]
Knowledge Transfer¶
The same two conditions transfer from a finite graph to a wireless graph model when radios are vertices and modeled links are undirected edges. What transfers is the test, not every physical assumption about radios. Live Connectedness names one required property but is not a strict parent of the selected dominating-set object; no DAG edge is staged. The separate redirected candidate “Connected domination number” remains an identity hold rather than an alias, and a broader cross-domain connected-cover skeleton is a future-prime question.[ref-c15991172f95][ref-fd89078d4b3f]
[^ref-c15991172f95]: Yair Caro, Douglas B. West, and Raphael Yuster, “Connected Domination and Spanning Trees with Many Leaves”, original authored paper, Abstract and §1 Introduction (PDF pp. 1–2). [^ref-fd89078d4b3f]: Peng-Jun Wan, Khaled M. Alzoubi, and Ophir Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks”, original INFOCOM research paper, Abstract and §I Introduction (PDF pp. 1–2).
Neighborhood in Abstraction Space¶
Connected Dominating Set sits in a moderately populated region (45th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Induced Path — 0.88
- Even-hole-free graph — 0.87
- Biconnected Component — 0.87
- Hadwiger number — 0.86
- Graph Toughness — 0.86
Computed from structural-signature embeddings · 2026-10-08