tlooto

Connected domatic number

Connected domatic number

Answer complete0s

The connected domatic number of a graph, denoted

dc(G)d_c(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.


Formal Definition

In a connected graph

G=(V,E)G = (V, E)

, a connected dominating set (CDS) is a subset

D⊆VD \subseteq V

such that:

  • Every vertex
v∈V∖Dv \in V \setminus D

is adjacent to at least one vertex in

DD

(domination), and

  • The subgraph induced by
DD

,

G[D]G[D]

, is connected.

A connected domatic partition is a partition of

VV

into pairwise disjoint CDSs. The connected domatic number

dc(G)d_c(G)

is the largest integer

kk

such that

VV

can be partitioned into

kk

disjoint 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}d_c(G) = \max \{k: V = D_1 \cup D_2 \cup \cdots \cup D_k, \; D_i \cap D_j = \emptyset \text{ for } i \neq j, \; \text{and each } D_i \text{ is a CDS}\}

Note: For disconnected graphs,

dc(G)d_c(G)

is not defined, as a CDS cannot exist for the entire vertex set[1].


Fundamental Properties

  • By definition,
dc(G)≤d(G)d_c(G) \leq d(G)

, the (ordinary) domatic number, since every connected dominating set is a dominating set, but not necessarily vice versa.

dc(G)≥1d_c(G) \geq 1

for any connected graph, since

VV

itself always forms a CDS[1].

dc(G)d_c(G)

is closely tied to graph connectivity: For instance, vertex connectivity forms a lower bound constraint. If

GG

has vertex connectivity

κ\kappa

, then

dc(G)≤κd_c(G) \leq \kappa

(since each CDS must intersect every vertex cut)[1].


Complexity and Algorithms

Computational Hardness
  • *Computing
dc(G)d_c(G)

is NP-complete in general graphs[1][3].**

  • For special classes (e.g., planar graphs or unit disk graphs), knowledge on the domatic number or connected dominating set number has been extended, but the connected domatic number retains computational intractability in most cases[2][4].
Approximation

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:

  • Efficient (1 + 1/s)-approximation algorithms for minimum CDS are available for unit-disk graphs[5].
  • Distributed heuristics exist for finding CDSs in wireless networks[6][7].
  • For domatic partitions into CDSs, distributed algorithms using maximal independent set-based heuristics have been proposed, achieving provable lower bounds on the number of CDSs in specific graph models (e.g., unit-disk graphs with sufficient minimum degree)[3].

A relevant result for unit disk graphs is that when the minimum degree

δ\delta

is high (e.g.,

δ≥48\delta \geq 48

), the number of disjoint CDSs found by the distributed algorithm in [3] satisfies:

∣CDP∣≥⌊δ+1β(c+1)⌋−f,|{\text{CDP}}| \geq \left\lfloor \frac{\delta+1}{\beta(c+1)} \right\rfloor - f,

where

β≤2\beta \leq 2

,

c≤11c \leq 11

are constants depending on the graph, and

ff

is a small error term[3].

Extremal and Structural Bounds

The connected domatic number is sharply constrained by parameters like vertex connectivity and minimum degree[1]. For instance,

  • In a non-complete connected graph
GG

, each CDS must intersect every vertex cut; thus,

dc(G)≤d_c(G) \leq

(vertex connectivity of

GG

)[1].

  • For the complete graph
KnK_n

,

dc(Kn)=nd_c(K_n) = n

, since every singleton vertex is itself a CDS[1].

  • In general, determining nontrivial exact values for
dc(G)d_c(G)

remains difficult, but for specific graphs and high-degree conditions, bounds and constructive algorithms are known[2][3].


Applications

Connected domatic partitions have direct implications in network science, notably:

  • Wireless ad hoc and sensor networks: Domatic partitions into CDSs allow rotation of the virtual backbone, enabling energy saving and increasing fault tolerance. By switching among multiple CDSs, network lifetime and robustness are improved[3].
  • Clustering and redundancy: Multiple CDSs facilitate simultaneous operation of disjoint network backbones or scheduling of sleep/awake cycles for battery management.

Example and Nontrivial Observation

Consider the cycle

C6C_6

(6 vertices in a ring): its domatic number

d(C6)=2d(C_6) = 2

, but its connected domatic number

dc(C6)=1d_c(C_6) = 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].


Summary

The connected domatic number

dc(G)d_c(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].

References
  1. [1]

    ZELINKA, B. Connected domatic number of a graph. Mathematica Slovaca, 1986, 36(4): 387–392.

  2. [2]

    HARTNELL, B.; RALL, Douglas F. Connected domatic number in planar graphs. Czechoslovak Mathematical Journal, 2001, 51(1): 173–179. https://doi.org/10.1023/a:1013770108453.

  3. [3]

    MISRA, R.; MANDAL, C. Rotation of CDS via connected domatic partition in ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2009, 8(4): 488–499. https://doi.org/10.1109/tmc.2008.128.

  4. [4]

    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: 1–8. https://doi.org/10.1109/wiopt.2006.1666454.

  5. [5]

    CHENG, Xiuzhen, et al. A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networks. Networks, 2003, 42(4): 202–208. https://doi.org/10.1002/net.10097.

  6. [6]

    WAN, Pengjun; ALZOUBI, K.; FRIEDER, O. Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, 2002, 9: 141–149. https://doi.org/10.1109/infcom.2002.1019411.

  7. [7]

    ALZOUBI, K.; WAN, Pengjun; FRIEDER, O. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 2002, 4(1): 22–29. https://doi.org/10.1109/jcn.2002.6596929.

Application of connected domatic number

Answer complete0s

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.


1. Backbone Rotation and Energy Efficiency in Wireless Sensor and Ad Hoc Networks

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


2. Fault Tolerance, Redundancy, and Robustness

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


3. Scalability and Distributed Operation

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


4. Topology Control, Scheduling, and Quality of Service

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


5. Extensions: Clustering, Parallel Processing, and Resource Allocation

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


6. Theoretical and Structural Insights for Network Design

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


Application Summary Table

DomainApplication of Connected Domatic NumberSupporting References
Wireless Sensor/Ad Hoc NetworksBackbone rotation, energy balance, fault tolerance[1][2][3][4]
Topology Control & SchedulingDuty cycling, active backbone scheduling for coverage/connectivity[1][2]
Fault Tolerance & RobustnessRedundancy planning, resilience to failure or attack[1][2]
Clustering & Resource AllocationCommunicable clusterhead selection, parallel task partitioning[1][5]
Network Design & AnalysisInsuring 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.

References
  1. [1]

    MISRA, R.; MANDAL, C. Rotation of CDS via connected domatic partition in ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2009, 8(4): 488–499. https://doi.org/10.1109/tmc.2008.128.

  2. [2]

    PINO, Tayler; CHOUDHURY, Salimur; AL-TURJMAN, F. Dominating set algorithms for wireless sensor networks survivability. IEEE Access, 2018, 6: 17527–17532. https://doi.org/10.1109/access.2018.2819083.

  3. [3]

    WAN, Pengjun; ALZOUBI, K.; FRIEDER, O. Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, 2002, 9: 141–149. https://doi.org/10.1109/infcom.2002.1019411.

  4. [4]

    ALZOUBI, K.; WAN, Pengjun; FRIEDER, O. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 2002, 4(1): 22–29. https://doi.org/10.1109/jcn.2002.6596929.

  5. [5]

    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: 1–8. https://doi.org/10.1109/wiopt.2006.1666454.

  6. [6]

    ZELINKA, B. Connected domatic number of a graph. Mathematica Slovaca, 1986, 36(4): 387–392.

tlooto can make mistakes. Check important information against the original sources.