Fuzzy domination in graphs and its applications to cryptographic key generation
*Altaf Osman MulaniCorresponding authordraomulani.vlsi@gmail.comDepartment of Electronics & Telecommunication EngineeringSKN Sinhgad College of EngineeringPandharpur, Maharashtra, 413304, IndiaView full profile → , S. Jagadeeshjaaga.ssjec@gmail.comDepartment of Electronics & Communication EngineeringSridevi Women’s Engineering CollegeHyderabad, Telangana, 500075, IndiaView full profile → , Shweta Sadanand Salunkheshweta.salunkhe@bharatividyapeeth.eduDepartment of Electronics & Telecommunication EngineeringBharati Vidyapeeth’s College of Engineering for WomenPune, Maharashtra, 411043, IndiaView full profile → , K. Shivashankerkondoorushiva@gmail.comDepartment of Electrical EngineeringSKN Sinhgad College of EngineeringPandharpur, Maharashtra, 413304, IndiaView full profile → , Pravin Ganpatrao Gawandepravin.gawande@vit.eduDepartment of Electronics and Telecommunication EngineeringVishwakarma Institute of TechnologyPune, Maharashtra, 411037, IndiaView full profile → , Shivam Mahendra Shuklashivam.shukla269@gmail.comDepartment of Engineering Sciences and HumanitiesThakur Shree DPS College of Engineering & ManagementVasai, Maharashtra, 401208, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Oct 2025
- Published Online:
- 30 Sep 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2784
- Pages:
- 3563–3572
Abstract
The theory of domination in graphs has traditionally operated within the binary framework of classical graph theory, wherein a vertex either dominates a neighbour or does not. This paper introduces a comprehensive generalization through fuzzy domination, where vertex membership values σ: V → [0, 1] and edge membership functions μ: E → [0, 1] replace the crisp adjacency relation with graded influence. We define the fuzzy dominating set, fuzzy domination number γf(G), and prove tight upper and lower bounds relating γf(G) to the classical domination number γ(G) and the order n of the graph. The central contribution of this paper is a cryptographic key generation scheme that exploits the minimum fuzzy dominating set as a combinatorial entropy source. By encoding the dominating vertex set and its weighted cover structure into a seed-extraction function composed with a Merkle–Damgard hash chain, we construct a deterministic key generation algorithm whose security reduces to the hardness of computing minimum fuzzy dominating sets in sparse random graphs, a problem we show to be NP-hard via reduction from weighted set cover. Experimental evaluation on Erdos–Renyi random graphs with n ∈ {10, …, 100} vertices demonstrates that the proposed scheme achieves Shannon entropy of 7.9994 bits/byte, avalanche effect of 50.6 ± 0.28%, and a key space of 2384, outperforming three recent graph-theoretic key generation baselines. The paper additionally proves two new theorems on fuzzy domination in complete bipartite graphs and cycle graphs that are of independent mathematical interest.
Keywords
Subject Classifications
References
[1] M. Akram and W. A. Dudek, “Fuzzy graph public key exchange: A 384-bit construction,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 25, no. 3, pp. 712–731 (2022).
[2] R. A. Borzooei and H. Rashmanlou, “Complete fuzzy graphs and domination,” New Mathematics and Natural Computation, vol. 17, no. 2, pp. 341–358 (2021).
[3] S. Bhattacharya and A. Jain, “Domination polynomial-based block cipher,” International Journal of Network Security, vol. 22, no. 4, pp. 618–629 (2020).
[4] W. Chen and L. Wang, “XL algebraic attacks on degree-bounded graph ciphers,” IEEE Transactions on Information Theory, vol. 70, no. 5, pp. 3814–3827 (2024).
[5] P. Das and A. Choudhury, “Graph spectral PRNGs: NIST and TestU01 benchmarks,” in Proc. IEEE ICES, pp. 112–119 (2021).
[6] M. Firdaus and N. Aziz, “Gaussian vs. triangular membership in fuzzy graph key generation,” Cryptography, vol. 8, no. 2, Art. no. 18 (2024).
[7] R. Kumari and V. Singh, “Graph key generation vs. NIST P-384: A benchmark study,” Journal of Information Security and Applications, vol. 64, Art. no. 103072 (2022).
[8] T. Nguyen and H. Tran, “Precomputed domination catalogues for lightweight key generation,” IEEE Internet of Things Journal, vol. 10, no. 11, pp. 9841–9853 (2023).
[9] S. Salunkhe, A. O. Mulani, D. Shahane, M. Rana, S. M. Shukla, and M. M. Jadhav, “Secure image transmission using chaotic encryption and DWT watermarking on reconfigurable platform,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 29, no. 1, pp. 349–361 (2026).
[10] S. Park and J. Lee, “Linear approximations of domination S-boxes,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E107-A, no. 3, pp. 441–449 (2024).
[11] P. Pramanik, M. Pal, and S. Mondal, “Intuitionistic fuzzy domination,” Discrete Mathematics, Algorithms and Applications, vol. 16, no. 4, Art. no. 2350089 (2024).
[12] A. Rahman and M. Al-Khatib, “Graph homomorphism stream ciphers,” IEEE Access, vol. 11, pp. 72841–72854 (2023).
[13] K. R. Chaudhari, A. O. Mulani, M. P. Gajare, V. Jadhav, P. Yawle, and A. V. Bang, “Bit error rate analysis of various error correction codes with concatenated RS-convolutional codes,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 29, no. 1, pp. 199–214 (2026).
[14] S. Samanta, M. Akram, and M. Pal, “m-Polar fuzzy graphs and domination,” Symmetry, vol. 14, no. 3, Art. no. 598 (2022).
[15] R. Tiwari and N. Sharma, “Security reduction for fuzzy graph key generation,” IEEE Transactions on Information Forensics and Security, vol. 19, no. 2, pp. 1241–1253 (2024).
