Connected domatic number
Connected domatic number
Connected domatic number
Connected domatic number
The connected domatic number of a graph, denoted
dc(G), is a fundamental concept in graph theory that extends the classical notions of domination and domatic partition by also demanding connectivity within dominating sets. Here, we synthesize and expand upon the provided materials, addressing both theoretical underpinnings and practical implications.
In a connected graph
G=(V,E), a connected dominating set (CDS) is a subset
D⊆Vsuch that:
is adjacent to at least one vertex in
D(domination), and
,
G[D], is connected.
A connected domatic partition is a partition of
Vinto pairwise disjoint CDSs. The connected domatic number
dc(G)is the largest integer
ksuch that
Vcan be partitioned into
kdisjoint connected dominating sets[1][2].
Mathematically,
dc(G)=max{k:V=D1∪D2∪⋯∪Dk,Di∩Dj=∅ for i≠j,and each Di is a CDS}Note: For disconnected graphs,
dc(G)is not defined, as a CDS cannot exist for the entire vertex set[1].
for any connected graph, since
Vis closely tied to graph connectivity: For instance, vertex connectivity forms a lower bound constraint. If
Ghas vertex connectivity
κ, then
dc(G)≤κ(since each CDS must intersect every vertex cut)[1].
is NP-complete in general graphs[1][3].**
While the specific problem of maximizing connected domatic partitions is hard, most algorithmic research focuses on minimum connected dominating sets or on constructing some (not all) CDS partitions[3][5][6][7]. For instance:
A relevant result for unit disk graphs is that when the minimum degree
δis high (e.g.,
δ≥48), the number of disjoint CDSs found by the distributed algorithm in [3] satisfies:
∣CDP∣≥⌊β(c+1)δ+1⌋−f,where
β≤2,
c≤11are constants depending on the graph, and
fis a small error term[3].
The connected domatic number is sharply constrained by parameters like vertex connectivity and minimum degree[1]. For instance,
, each CDS must intersect every vertex cut; thus,
dc(G)≤(vertex connectivity of
G)[1].
,
dc(Kn)=n, since every singleton vertex is itself a CDS[1].
remains difficult, but for specific graphs and high-degree conditions, bounds and constructive algorithms are known[2][3].
Connected domatic partitions have direct implications in network science, notably:
Consider the cycle
C6(6 vertices in a ring): its domatic number
d(C6)=2, but its connected domatic number
dc(C6)=1, as any partition into two sets gives at least one set that is not connected. This demonstrates that connectivity requirement sharply reduces possible partitions[1].
The connected domatic number
dc(G)is the maximum number of pairwise disjoint connected dominating sets that partition the vertex set of a connected graph. It is deeply related to, but more restrictive than, the classic domatic number, as each part must induce a connected subgraph[1]. It is computationally intensive to find or even approximate for general graphs, leading to research into algorithms that provide effective partitions for classes like unit disk graphs, often using distributed or approximation approaches suitable for network applications[3][5]. This parameter plays a critical role in designing resilient, energy-efficient, and fault-tolerant wireless networks, and offers rich territory for algorithmic and structural graph theory[1][2][3].
ZELINKA, B. Connected domatic number of a graph. Mathematica Slovaca, 1986.
HARTNELL, B.; RALL, Douglas F. Connected domatic number in planar graphs. Czechoslovak Mathematical Journal, 2001. https://doi.org/10.1023/a:1013770108453.
MISRA, R.; MANDAL, C. Rotation of CDS via connected domatic partition in ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2009. https://doi.org/10.1109/tmc.2008.128.
NGUYEN, Trac N.; HUYNH, D. Connected d-hop dominating sets in mobile ad hoc networks. 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006. https://doi.org/10.1109/wiopt.2006.1666454.
CHENG, Xiuzhen, et al. A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networks. Networks, 2003. https://doi.org/10.1002/net.10097.
WAN, Pengjun; ALZOUBI, K.; FRIEDER, O. Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, 2002. https://doi.org/10.1109/infcom.2002.1019411.
ALZOUBI, K.; WAN, Pengjun; FRIEDER, O. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 2002. https://doi.org/10.1109/jcn.2002.6596929.
Application of connected domatic number
Application of connected domatic number
The connected domatic number—the largest number of pairwise disjoint connected dominating sets that partition the nodes of a connected graph—has substantial practical applications, particularly where both coverage and connectivity are foundational requirements.
Wireless sensor networks (WSNs) and mobile ad hoc networks (MANETs) are often modeled as graphs where nodes represent devices and edges represent direct communication. In such systems, a connected dominating set (CDS) forms a virtual backbone for routing and information dissemination, as it assures both reachability (domination) and communication paths (connectivity).
However, serving as part of the CDS incurs increased energy expenditure, accelerating battery depletion. To balance the energy load and avoid early network partition, the network is periodically restructured so a different, disjoint CDS plays the backbone role—this is only possible when multiple disjoint CDSs exist, the maximum being governed by the connected domatic number. Hence, the higher the connected domatic number, the longer the overall network can function by rotating through these CDSs, with each node fairly sharing the load over time. Misra & Mandal's distributed algorithms illustrate this principle, providing scalable means to compute such partitions and empirically demonstrating improved lifetime in large-scale networks[1]. Similar principles underlie sleep-wake and duty cycling schemes, which leverage disjoint CDSs to maintain coverage and connectivity with only a portion of nodes awake at a time, drastically improving energy efficiency[2].
Multiple disjoint connected dominating sets facilitate fault tolerance. If one CDS fails due to node mobility, battery exhaustion, or attack, alternative CDSs can be activated in rotation with no loss of global connectivity or coverage. This redundancy is crucial for resilient operation in critical applications (e.g., environmental monitoring, emergency response), such that the network can dynamically adapt and reconfigure routing structures to circumvent failures[1][2].
Moreover, with an increased connected domatic number, the system's resistance to targeted attacks or random failures grows, since more non-overlapping sets of nodes are capable of maintaining the backbone property, preserving connectivity and monitoring abilities[1].
The process of identifying CDSs and performing connected domatic partitions is central to scalable and distributed networking protocols. Modern distributed algorithms directly construct these structures without requiring centralized control or full topology knowledge, satisfying real-time constraints in large, dynamic networks[3][4]. Such algorithms are foundational in self-organizing network systems, as they enable the network to adapt to topology changes (due to node mobility or varying link quality) while continuing to uphold guarantees on coverage and connectivity[1][5].
Topology control protocols often rely on selecting a subset of nodes (CDS) to reduce interference and conserve power while maintaining network integrity. By partitioning the nodes into several CDSs, nodes take turns performing communication-heavy roles, making scheduling more efficient and ultimately delivering better Quality of Service (QoS) by preventing overloading of certain nodes and ensuring that coverage is sustained at all times[1].
In duty-cycled WSNs, scheduling tasks using the connected domatic number ensures that, in every time slot, a connected dominating set is active, thus preserving both network coverage and communication despite resource constraints. This approach minimizes latency for routing and data collection, as the backbone is always maintained[1][2].
In both wireless and parallel computation domains, dividing networks into CDSs (up to the connected domatic number) allows for resource partitioning into communicable subgroups, facilitating load balancing, parallel task allocation, and modular configuration for monitoring or surveillance[5]. In clustering algorithms, such as d-hop clustering in ad hoc networks, the connected domatic number informs the design of clusterheads and cluster structures, providing guarantees on interconnectivity and coverage even as the network scales or evolves[5].
The connected domatic number is intricately linked to the graph's vertex connectivity and minimum degree, serving as a design constraint: it cannot exceed the vertex connectivity of the underlying graph[6]. This relationship provides a blueprint for building robust infrastructure—with higher vertex connectivity, more CDSs (and thus more backbone rotations and higher resilience) are possible[1][6].
| Domain | Application of Connected Domatic Number | Supporting References |
|---|---|---|
| Wireless Sensor/Ad Hoc Networks | Backbone rotation, energy balance, fault tolerance | [1][2][3][4] |
| Topology Control & Scheduling | Duty cycling, active backbone scheduling for coverage/connectivity | [1][2] |
| Fault Tolerance & Robustness | Redundancy planning, resilience to failure or attack | [1][2] |
| Clustering & Resource Allocation | Communicable clusterhead selection, parallel task partitioning | [1][5] |
| Network Design & Analysis | Insuring backbone redundancy by design, leveraging vertex connectivity relation | [1][6] |
In summary, the connected domatic number acts as both a combinatorial measure and a practical enabler for efficient, robust, and sustainable deployment in networked systems—particularly in settings where connectivity, redundancy, and fairness in resource utilization are imperative[1][2][3][4][5][6]. By guiding the construction and rotation of virtual backbones, it underpins essential strategies for modern ad hoc, sensor, and distributed computational networks.
MISRA, R.; MANDAL, C. Rotation of CDS via connected domatic partition in ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2009. https://doi.org/10.1109/tmc.2008.128.
PINO, Tayler; CHOUDHURY, Salimur; AL-TURJMAN, F. Dominating set algorithms for wireless sensor networks survivability. IEEE Access, 2018. https://doi.org/10.1109/access.2018.2819083.
WAN, Pengjun; ALZOUBI, K.; FRIEDER, O. Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, 2002. https://doi.org/10.1109/infcom.2002.1019411.
ALZOUBI, K.; WAN, Pengjun; FRIEDER, O. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 2002. https://doi.org/10.1109/jcn.2002.6596929.
NGUYEN, Trac N.; HUYNH, D. Connected d-hop dominating sets in mobile ad hoc networks. 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006. https://doi.org/10.1109/wiopt.2006.1666454.
ZELINKA, B. Connected domatic number of a graph. Mathematica Slovaca, 1986.
tlooto can make mistakes. Check important information against the original sources.