Minimum Connected Domination in Fuzzy Graphs: Theory, Algorithms, and Applications

Minimum connected domination is an important optimization problem in graph theory with applications in communication networks, facility location, routing, monitoring, and decision-making. Classical graphs assume that every relation between two vertices is either present or absent; however, many practical networks involve connections that are uncertain, unreliable, or partially available. Fuzzy graphs provide a suitable framework for representing such uncertainty through VM and EM values.This study develops a threshold-based mathematical framework for the MCD in fuzzy graphs. The concept of an α-connected dominating set is introduced using the α-cut of a fuzzy graph. The fundamental properties, bounds, and monotonicity results are established. A greedy connected fuzzy domination algorithm is proposed to construct a small connected dominating set while considering the strength and connectivity of fuzzy domination. The correctness and computational complexity of the proposed algorithm are discussed. An illustrative numerical example demonstrates the proposed method. Applications to wireless sensor networks, emergency communication systems, transportation networks, and facility-location problems are also presented. The framework preserves the original fuzzy network’s uncertainty information while enabling efficient combinatorial analysis.