Connected Dominating Set¶

A vertex subset of an undirected graph that dominates every excluded vertex while inducing a connected subgraph on its selected vertices.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13084
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Theory, Domination Theory → Mathematics

Core Idea¶

In a finite simple undirected graph $G=(V,E)$, a connected dominating set (CDS) is a nonempty vertex subset $D\subseteq V$ satisfying two tests. Every vertex outside $D$ has a neighbor in $D$; and the subgraph $G[D]$ induced by the selected vertices is connected. The first test gives one-edge coverage of the unselected vertices. The second gives paths within the selected subset itself. Full-graph connectedness, or either test alone, is insufficient.^[1]

The definition identifies an eligible set, not necessarily a smallest one. The connected domination number $\gamma_c(G)$ is the separate minimum of $|D|$ over eligible sets of a connected graph. Thus $D=V$ can be a CDS even when many of its vertices are dispensable. This distinction matters because an application may need a working connected backbone without having solved the harder minimum-cardinality problem.^[1]^[2]

The pattern has a mathematical and a model-based network interpretation. In graph theory, it couples vertex domination with an induced connected subgraph. In an undirected unit-disk model of wireless radios, selected radios can be treated as a connected virtual backbone while every unselected radio is adjacent to a selected one. The network interpretation depends on that declared graph model; it is not an assertion that every physical radio link is symmetric or unit-disk.^[2]

Structural Signature¶

Sig role-phrases: finite undirected graph and adjacency — selected vertex subset — domination of excluded vertices — induced connectivity of selected vertices — optional cardinality optimization.

Finite undirected graph and adjacency. Vertices and edges fix what one-hop neighbor and induced path mean. Weighted or directed variants may be useful but need their own rules; they do not silently inherit this predicate.^[1]
Selected vertex subset. $D$ distinguishes backbone members from the rest of $V$. Merely saying that $G$ is connected does not identify a CDS witness, although for a connected graph the full nonempty set $V$ is always one.^[1]
Domination of excluded vertices. For every $v\in V\setminus D$ there is $u\in D$ with $uv\in E$. A selected subgraph can be perfectly connected and still fail this coverage test.^[1]
Induced connectivity of selected vertices. Every pair in $D$ can be joined by a path whose vertices all lie in $D$. A path using unselected vertices does not repair a disconnected $G[D]$.^[1]
Optional cardinality optimization. Seeking small $|D|$ or the minimum $\gamma_c(G)$ can reduce the size of a backbone. It is not a condition for CDS membership: a larger eligible $D$ remains a CDS.^[1]^[2]

The first four roles decide membership. The fifth decides an additional optimization claim. If an excluded vertex loses all selected neighbors, domination fails; if selected vertices split into components, connectivity fails. By contrast, adding a redundant selected vertex to an eligible CDS may destroy minimality without destroying eligibility, provided the enlarged selected subgraph remains connected.

What It Is Not¶

A CDS is not just a dominating set. In the path $1-2-3-4-5$, $\{2,4\}$ dominates every excluded vertex, including $3$, but $G[\{2,4\}]$ has no edge. It is not connected. Adding $3$ yields $\{2,3,4\}$, which meets both tests.^[1]

Nor is it merely a connected induced subgraph: a chosen path segment might leave a vertex outside it with no selected neighbor. The existence of paths in the full graph does not guarantee paths using only chosen vertices. It is not a connected domination number, which is a minimum cardinality and hence an isomorphism-invariant numerical property of a graph. The independently queued Wikipedia title “Connected domination number” redirects to the set article, but that redirect does not establish synonymy between the object and the number.^[1]

A CDS also differs from a domatic partition, which divides all vertices into several dominating blocks, and from a moving-guard or eternal-domination configuration, whose reconfiguration requirements are not part of CDS membership. A wireless virtual-backbone algorithm is a way to find or use a CDS under a chosen network model, not the graph object itself.^[2]

Scope of Application¶

For a connected finite simple undirected graph, the full vertex set provides an immediate CDS witness, while finding a minimum one is a separate optimization task. On a disconnected graph, no one selected connected subset can dominate vertices in all components; the ordinary whole-graph CDS definition therefore has no witness. The convention for an empty graph should be stated separately rather than hidden inside the nonempty-set definition.^[1]

In graph algorithms, CDSs connect to spanning trees. For a connected graph with at least three vertices, the nonleaf vertices of a spanning tree form a CDS. Conversely, a CDS can be used to build a spanning tree with its excluded vertices among the leaves. Therefore the optimum values obey $\gamma_c(G)+L(G)=|V|$, where $L(G)$ is the maximum number of leaves in a spanning tree. This does not say that every particular CDS and every arbitrary spanning tree form an exact complementary pair.^[1]

In Wan, Alzoubi and Frieder's wireless-ad-hoc-network model, a link exists when radios are within a stipulated unit range, yielding an undirected unit-disk graph. A connected dominating subset acts as a virtual backbone for routing, broadcasting, and related graph-level coordination. The paper studies distributed construction and distinguishes obtaining a CDS from minimizing one; it does not establish that a single static backbone remains valid under every real-world link change.^[2]

Clarity¶

An auditable claim names $G$, specifies its adjacency convention, displays $D$, and checks two different relations. For vertices outside $D$, check direct adjacency to at least one member of $D$; a multihop route is not domination. For vertices inside $D$, check multihop reachability using only selected vertices; paths through excluded vertices do not make $G[D]$ connected.^[1]

It also says whether “minimum” is claimed. Showing the two membership tests certifies only a CDS. To assert $\gamma_c(G)$, one needs a lower bound ruling out every smaller eligible set as well. Likewise, a thin wireless backbone is a design preference, not part of the mathematical definition.^[1]^[2]

Manages Complexity¶

The abstraction replaces a potentially large pattern of local contacts with a two-part certificate. A selected subset can simultaneously offer one-hop access from outsiders and an internally traversable skeleton. Network design can then reason at the selected-backbone level while retaining the explicit adjacency test at its boundary. This compression is legitimate only for the stated graph model: physical interference, asymmetric radios, capacity, and failures are not encoded by an unqualified simple undirected edge.^[2]

The optimization layer adds a different burden. A small eligible set may reduce the number of designated backbone vertices, while constructing it in a distributed setting can require communication and computation. Wan and colleagues analyze construction costs and the desirability of a thin backbone; they do not make minimum size a prerequisite for a usable CDS. The distinction allows a larger but established witness to remain meaningful while optimization is studied separately.^[2]

Abstract Reasoning¶

The predicate is a conjunction: $\mathrm{CDS}(D)$ holds exactly when $\mathrm{Dom}(D)$ and $\mathrm{Conn}(G[D])$ both hold. This factorization gives two independent failure tests. On $P_5$, $D=\{2,4\}$ has domination but not induced connectivity. If a connected selected segment on a longer path stops too far from an endpoint, it can have induced connectivity but fail domination. One should repair the failed condition rather than infer the other from graph-wide connectedness.^[1]

The spanning-tree correspondence exposes a useful change of viewpoint. To maximize leaves, keep fewer internal tree vertices; those internal vertices form a CDS when $|V|\geq3$. Conversely, start with a connected tree on a CDS and attach each outsider by one of its guaranteed edges into $D$. The outsiders then become leaves. This construction explains an equality between extrema, not an identity between an arbitrary chosen $D$ and the internal set of every possible tree.^[1]

Knowledge Transfer¶

The graph-theoretic eligibility test transfers intact to the declared unit-disk network model: radios become vertices, modeled communication links become edges, selected backbone radios are $D$, outsiders must have a one-hop link into $D$, and selected radios must connect among themselves. The transfer is useful precisely because it preserves both tests. Merely transplanting the word “backbone” into a setting with directed, intermittent or unreliable links would leave the required adjacency and connectivity conventions unproved.^[2]

The maximum-leaf relation transfers a problem rather than a word. Optimizing a CDS can be recast as optimizing the number of spanning-tree leaves on a connected graph of at least three vertices. The values complement, but the chosen tree and chosen set still require construction and verification. This is why the relation can guide algorithms without turning a CDS into a spanning tree or a graph invariant.^[1]

Examples¶

A path and a star. On $P_5$ with edges $1-2-3-4-5$, take $D=\{2,3,4\}$. The excluded endpoints $1$ and $5$ meet $D$ at $2$ and $4$, and $G[D]$ is the connected path $2-3-4$. No two-vertex subset can both dominate the endpoints and connect across the path, so this particular CDS is minimum. On the five-vertex star $K_{1,4}$, the center alone is a CDS: every leaf touches it and a singleton induced graph is connected. These are transparent constructions from the original definition, not additional results attributed to its authors.^[1] Mapped back: finite undirected graph and adjacency = the path or star edges; selected vertex subset = three internal path vertices or the star center; domination of excluded vertices = endpoints or leaves each touch a selected vertex; induced connectivity of selected vertices = the selected path segment or singleton; optional cardinality optimization = both examples happen to be minimum, whereas the full vertex set is another, generally nonminimum, CDS.

A model-based radio backbone. Wan, Alzoubi and Frieder use an undirected unit-disk graph for a wireless ad hoc network and seek a connected dominating subset for a virtual backbone. A non-backbone radio has at least one directly adjacent backbone radio; the backbone radios can connect through other backbone radios. Their distributed algorithms seek a relatively thin connected backbone without changing the eligibility tests.^[2] Mapped back: finite undirected graph and adjacency = stipulated pairwise unit-range radio links in the model; selected vertex subset = backbone radios; domination of excluded vertices = every non-backbone radio has a one-hop modeled link to a selected radio; induced connectivity of selected vertices = forwarding paths using selected-radio links alone; optional cardinality optimization = a smaller backbone is an additional design objective, not the definition of a CDS.

Structural Tensions¶

Small backbone versus construction cost. The mathematical minimum makes the selected core as small as possible. In a distributed network, constructing a small backbone involves communication and computation; a larger already established CDS may still pass both graph tests. This is a real choice between an optimization objective and the cost of attaining it, not a claim that larger is always preferable or that the cited construction paper analyzed ongoing maintenance.^[2] Diagnostic: Is the current task to certify some connected dominating backbone, or to justify a minimum or near-minimum one at an acceptable construction cost?

Coverage versus selected-set connectivity. Choosing few vertices to cover outsiders can leave selected islands. On $P_5$, $\{2,4\}$ is a two-vertex dominating set; connecting its selected vertices by adding $3$ increases size to three. Yet in another graph a small dominating set may already be connected, so the penalty is topology-dependent. Caro, West and Yuster explicitly bound the extra vertices required to join components of a dominating set in their mathematical analysis.^[1] Diagnostic: Does the selected subset itself have a path between every pair, or is apparent connectivity borrowed from unselected vertices?

Structural–Framed Character¶

Connected Dominating Set lies near the structural end of the spectrum within a specifically graph-theoretic frame. Its two membership tests are exact and portable across graph instances, but undirected vertices, adjacency, and induced subgraphs are constitutive, not removable context. Evaluative weight: eligibility is a formal yes/no predicate; “better” or “thin” enters only with a size or deployment objective. Human-practice dependence: people choose models and backbones, but whether a displayed $D$ passes the stated tests does not depend on preference. Institutional origin: graph-theory and networking communities use the term, yet institutional endorsement is not what makes a witness valid. Vocabulary travel: the same predicate travels from extremal graph theory to unit-disk network models, while loose uses of “backbone” do not automatically count. Import versus recognition: in a network model one recognizes an actual CDS only after checking its edges and selected paths; importing the label without an adequate graph model would be an unsupported extension.^[1]^[2]

Its character: a highly formal domain-specific structural abstraction: it is more than a network-design tactic, but it is not the substrate-independent idea of “a connected covering core” promoted into a prime.

Structural Core vs. Domain Accent¶

The core is a selected subset that directly covers all excluded vertices and is internally connected. The domain-bound mechanism is the conjunction of graph domination by adjacency and connectivity of an induced subgraph. The star, path, and modeled radio network change what vertices and edges denote; they do not change the predicate. Minimum size, a virtual-backbone algorithm, and a particular radio-range model are accents or downstream objectives rather than membership roles.^[1]^[2]

If vertices, graph edges, and one-hop domination are abstracted away, a portable “connected cover” pattern may remain. Whether that deserves a cross-domain prime is an explicit future-prime question; the present evidence does not establish a necessary strict edge to live Connectedness, which is a property of a structured whole rather than the genus of selected dominating vertex sets.

No strict typed parent relation is asserted in the current DAG. The inspected live graph and connectedness identities do not supply a necessary typed genus for a selected vertex subset satisfying both domination and induced connectivity. The connected domination number is a separate numerical invariant, not a parent or alias of the set.

Neighborhood in Abstraction Space¶

Connected Dominating Set sits in a moderately populated region (45^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Structures & Combinatorial Objects (44 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

A dominating set lacking connectivity: $\{2,4\}$ on $P_5$ covers the path but its selected vertices do not touch.^[1]
A connected subset lacking domination: internal connected paths need not reach every excluded vertex in one edge.^[1]
The connected domination number: $\gamma_c(G)$ is the minimum size over all CDSs, not one particular eligible set.^[1]
A minimum connected dominating set: one special CDS attaining $\gamma_c(G)$; most eligible sets need not be minimum.^[1]
A domatic partition or eternal domination strategy: partition count and time-evolving guard defense impose different structures.
A physical network independent of modeling assumptions: the original wireless example assumes a specified undirected unit-disk graph, not arbitrary asymmetric or changing links.^[2]
Maximum-leaf spanning tree: a related optimization problem with an optimum-value complementarity for connected graphs of at least three vertices; the objects are not synonyms.^[1]

References¶

[1] 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), especially the definitions, spanning-tree correspondence, and Lemma 2.1. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y

[2] 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), including the unit-disk model, virtual-backbone role, and construction-cost discussion. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n