Optimal secret share distribution in degree splitting communication networks

Raúl M. Falcón; Venkitachalam Aparna; Nagaraj Mohanapriya; Raúl M. Falcón; Venkitachalam Aparna; Nagaraj Mohanapriya

doi:10.3934/nhm.2023075

Networks and Heterogeneous Media

2023, Volume 18, Issue 4: 1713-1746. doi: 10.3934/nhm.2023075

Previous Article Next Article

Research article

Optimal secret share distribution in degree splitting communication networks

1.
Department of Applied Mathematics I, University of Seville, Avda. Reina Mercedes 4A, Seville, 41012, Spain
2.
PG and Research Department of Mathematics, Kongunadu Arts and Science College, GN Mills, Tamil Nadu, 641 029, Coimbatore, India

Received: 14 March 2023 Revised: 02 October 2023 Accepted: 08 October 2023 Published: 13 October 2023

Dynamic coloring has recently emerged as a valuable tool to optimize cryptographic protocols based on secret sharing, which enforce data security in communication networks and have significant importance in both online storage and cloud computing. This type of graph labeling enables the dealer to distribute secret shares among the nodes of a communication network so that everybody can recover the secret after a minimum number of rounds of communication. This paper delves into this topic by dealing with the dynamic coloring problem for degree splitting graphs. The topological structure of the latter enables the dealer to avoid dishonesty by adding control nodes that supervise all those participants with a similar influence in the network. More precisely, we solve the dynamic coloring problem for degree splitting graphs of any regular graph. The irregular case is partially solved by establishing a lower bound for the corresponding dynamic chromatic number. As illustrative examples, we solve the dynamic coloring problem for the degree splitting graphs of cycles, cocktail, book, comb, fan, jellyfish, windmill and barbell graphs.
- Degree splitting networks,
- secret sharing,
- dynamic coloring problem
Citation: Raúl M. Falcón, Venkitachalam Aparna, Nagaraj Mohanapriya. Optimal secret share distribution in degree splitting communication networks[J]. Networks and Heterogeneous Media, 2023, 18(4): 1713-1746. doi: 10.3934/nhm.2023075

Related Papers:

Abstract

Dynamic coloring has recently emerged as a valuable tool to optimize cryptographic protocols based on secret sharing, which enforce data security in communication networks and have significant importance in both online storage and cloud computing. This type of graph labeling enables the dealer to distribute secret shares among the nodes of a communication network so that everybody can recover the secret after a minimum number of rounds of communication. This paper delves into this topic by dealing with the dynamic coloring problem for degree splitting graphs. The topological structure of the latter enables the dealer to avoid dishonesty by adding control nodes that supervise all those participants with a similar influence in the network. More precisely, we solve the dynamic coloring problem for degree splitting graphs of any regular graph. The irregular case is partially solved by establishing a lower bound for the corresponding dynamic chromatic number. As illustrative examples, we solve the dynamic coloring problem for the degree splitting graphs of cycles, cocktail, book, comb, fan, jellyfish, windmill and barbell graphs.

References

[1]	G. R. Blakley, Safeguarding cryptographic keys, Managing Requirements Knowledge, International Workshop on. IEEE Computer Society, (1979), 313–317. https://doi.org/10.1109/MARK.1979.8817296 doi: 10.1109/MARK.1979.8817296
[2]	A. Shamir, How to share a secret, Comm. ACM, 22 (1979), 612–613. https://doi.org/10.1145/359168.359176 doi: 10.1145/359168.359176
[3]	V. Attasena, J. Darmont, N. Harbi, Secret sharing for cloud data security, VLDB J., 26 (2017), 657–681. https://doi.org/10.1007/s00778-017-0470-9 doi: 10.1007/s00778-017-0470-9
[4]	L. Ogiela, M. R. Ogiela, H. Ko, Intelligent data management and security in cloud computing. Sensors, 20 (2020), 3458. https://doi.org/10.3390/s20123458 doi: 10.3390/s20123458
[5]	S. Sallinen, K. Iwabuchi, S. Poudel, M. Gokhale, M. Ripeanu, R. Pearce, Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage, and Analysis (SC'16), IEEE, Los Alamitos, CA, (2016), 347–358. https://doi.org/10.1109/SC.2016.29
[6]	Q. Y. Hu, C. Wen, T. Z. Huang, Z. L. Shen, X. M. Gu, A variant of the Power-Arnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 381 (2021), 113034. https://doi.org/10.1016/j.cam.2020.113034 doi: 10.1016/j.cam.2020.113034
[7]	M. E. Coimbra, A. P. Francisco, L. Veiga, An analysis of the graph processing landscape, J. Big Data, 8 (2021), 55. https://doi.org/10.1186/s40537-021-00443-9 doi: 10.1186/s40537-021-00443-9
[8]	Z. Tuza, Graph colorings with local constraints—a survey, Discuss. Math. Graph Theory, 17 (1997), 161–228. https://doi.org/10.7151/dmgt.1049 doi: 10.7151/dmgt.1049
[9]	P. Formanowicz, K. Tanaś, A survey of graph coloring - its types, methods and applications, Found. Comput. Decision Sci., 37 (2012), 223–238. https://doi.org/10.2478/v10209-011-0012-y doi: 10.2478/v10209-011-0012-y
[10]	R. M. R. Lewis, Guide to graph colouring—algorithms and applications, Cham: Springer, (2021). https://doi.org/10.1007/978-3-030-81054-2
[11]	S. Labed, A. Kout, S. Chikhi, Solving the graph $b$-coloring problem with hybrid genetic algorithm, 3rd International Conference on Pattern Analysis and Intelligent Systems (PAIS 2018), (2018), 1–7. https://doi.org/10.1109/PAIS.2018.8598525 doi: 10.1109/PAIS.2018.8598525
[12]	E. F. Olariu, C. Frăsinaru, Improving lower bounds for equitable chromatic number, Comput. Oper. Res., 143 (2022), 105790. https://doi.org/10.1016/j.cor.2022.105790 doi: 10.1016/j.cor.2022.105790
[13]	Y. Imine, H. Lakhlef, M. Raynal, F. Taïani, DMCSC: a fully distributed multi-coloring approach for scalable communication in synchronous broadcast networks, J. Supercomput., 79 (2023), 788–813. https://doi.org/10.1007/s11227-022-04700-3 doi: 10.1007/s11227-022-04700-3
[14]	Y. Shang, Concentration of rainbow $k$-connectivity of a multiplex random graph, Theoret. Comput. Sci., 951 (2023), 113771. https://doi.org/10.1016/j.tcs.2023.113771 doi: 10.1016/j.tcs.2023.113771
[15]	S. Roy, A. S. Sairam, Distributed star coloring of network for IP traceback, Int. J. Inf. Secur., 17 (2018), 315–326. https://doi.org/10.1007/s10207-017-0366-0 doi: 10.1007/s10207-017-0366-0
[16]	R. M. Falcón, N. Mohanapriya, V. Aparna, Optimal shadow allocations of secret sharing schemes arisen from the dynamic coloring of extended neighborhood coronas, Mathematics, 10 (2022), 2018. https://doi.org/10.3390/math10122018 doi: 10.3390/math10122018
[17]	B. Montgomery, Dynamic Goloring of Graphs, Doctoral Thesis of West Virginia University, Morgantown, 2001.
[18]	X. Li, X. Yao, W. Zhou, H. Broersma, Complexity of conditional colorability of graphs, Appl. Math. Lett., 22 (2009), 320–324. https://doi.org/10.1016/j.aml.2008.04.003 doi: 10.1016/j.aml.2008.04.003
[19]	A. S. Akbari, A. Dehghana, M. Ghanbari, On the difference between chromatic and dynamic chromatic number of graphs, Discrete Math., 312 (2012), 2579–2583. https://doi.org/10.1016/j.disc.2011.09.006 doi: 10.1016/j.disc.2011.09.006
[20]	M. Alishahi, Dynamic chromatic number of regular graphs, Discrete Appl. Math., 160 (2012), 2098–2103. https://doi.org/10.1016/j.dam.2012.05.017 doi: 10.1016/j.dam.2012.05.017
[21]	V. Aparna, N. Mohanapriya, On $r$-dynamic coloring of some graphs, Kong. Res. J., 7 (2020), 82–87. https://doi.org/10.26524/krj.2020.13 doi: 10.26524/krj.2020.13
[22]	T. Deepa, R. M. Falcón, M. Venkatachalam, On the $r$-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph, AIMS Math, 6 (2021), 1470–1496. https://doi.org/10.3934/math.2021090 doi: 10.3934/math.2021090
[23]	R. M. Falcón, S. Gowri, M. Venkatachalam, Solving the dynamic coloring problem for direct products of paths with fan graphs, Analele Stiintifice ale Univ. Ovidius Constanta, Ser. Mat., 31 (2023), 115–142. https://doi.org/10.2478/auom-2023-0006 doi: 10.2478/auom-2023-0006
[24]	K. Kaliraj, H. Naresh, Kumar, J. Vernold Vivin, On dynamic colouring of Cartesian product of complete graph with some graphs, J. Taibah Univ. Sci., 14 (2020), 168–171. https://doi.org/10.1080/16583655.2020.1713586 doi: 10.1080/16583655.2020.1713586
[25]	H. J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin., 68 (2003), 193–201.
[26]	H. J. Lai, B. Montgomery, Z. Tao, Conditional colorings of graphs, Discrete Math., 306 (2006), 1997–2004. https://doi.org/10.1016/j.disc.2006.03.052 doi: 10.1016/j.disc.2006.03.052
[27]	J. Vernold Vivin, N. Mohanapriya, J. Kok, M. Venkatachalam, On dynamic coloring of certain cycle-related graphs, Arab. J. Math., 9 (2020), 213–221. https://doi.org/10.1007/s40065-018-0219-3 doi: 10.1007/s40065-018-0219-3
[28]	G. Nandini, M. Venkatachalam, R. M. Falcón, On the $r$-dynamic coloring of subdivision-edge coronas of a path, AIMS Math, 5 (2020), 4546–4562. https://doi.org/10.3934/math.2020292 doi: 10.3934/math.2020292
[29]	J. V. Vivin, N. Mohanapriya, J. Kok, M. Venkatachalam, On dynamic coloring of certain cycle-related graphs, Arab. J. Math., 9 (2020), 213–221. https://doi.org/10.1007/s40065-018-0219-3 doi: 10.1007/s40065-018-0219-3
[30]	T. Deepa, M. Venkatachalam, Dafik, On $r$-dynamic coloring of the gear graph families, Proyecciones, 40 (2021), 1–15. http://dx.doi.org/10.22199/issn.0717-6279-2021-01-0001 doi: 10.22199/issn.0717-6279-2021-01-0001
[31]	R. M. Falcón, M. Venkatachalam, S. Gowri, G. Nandini, On the $r$-dynamic coloring of some fan graph families, Analele Stiintifice ale Univ. Ovidius Constanta, Ser. Mat., 29 (2021), 151–181. https://doi.org/10.2478/auom-2021-0039 doi: 10.2478/auom-2021-0039
[32]	K. Kalaiselvi, N. Mohanapriya, V. Aparna, $r$-Dynamic chromatic number of subdivision-edge neighborhood corona of certain graph families, Discrete Math. Algorithms Appl., (2023), 2350026. https://doi.org/10.1142/S179383092350026X doi: 10.1142/S179383092350026X
[33]	G. Nandini, M. Venkatachalam, J. Vernold Vivin, On $r$-dynamic coloring of $n$-sunlet graph families, Proc. Jangjeon Math. Soc., 26 (2023), 23–42. http://dx.doi.org/10.17777/pjms2023.26.1.23 doi: 10.17777/pjms2023.26.1.23
[34]	Y. Chen, S. Fan, H. J. Lai, M. Xu, Graph $r$-hued colorings–A survey, Discret. Appl. Math., 321 (2022), 24–48. https://doi.org/10.1016/j.dam.2022.06.003 doi: 10.1016/j.dam.2022.06.003
[35]	J. Kim, S. Ok, Dynamic choosability of triangle-free graphs and sparse random graphs, J. Graph Theory, 87, (2017), 347–355. https://doi.org/10.1002/jgt.22161 doi: 10.1002/jgt.22161
[36]	R. Ponraj, S. Somasundaram, On the degree splitting graph of a graph, Natl. Acad. Sci. Lett., 27 (2004), 275–278.
[37]	F. Harary, Graph Theory, Boulder: Westview Press, 1969.
[38]	K. D. Mackenzie, Decomposition of communication networks, J Math Psychol, 4 (1967), 162–174. https://doi.org/10.1016/0022-2496(67)90048-X doi: 10.1016/0022-2496(67)90048-X
[39]	D. Angel, I. A. Arputhamary, R. Revathi, M. Nirmala, Secure node covering of cocktail party graphs and generalized fan graphs. 2022 Third International Conference on Intelligent Computing Instrumentation and Control Technologies (ICICICT), (2022), 261–264. https://doi.org/10.1109/ICICICT54557.2022.9918002 doi: 10.1109/ICICICT54557.2022.9918002
[40]	B. Basavanagoud, P. Jakkannavar, Praveen, S. Policepatil, Integrity of total transformation graphs, Electron. J. Graph Theory Appl., 9 (2021), 309–329. https://doi.org/10.5614/ejgta.2021.9.2.6 doi: 10.5614/ejgta.2021.9.2.6
[41]	A. Bassolas, V. Nicosia, First-passage times to quantify and compare structural correlations and heterogeneity in complex systems, Commun. Phys., 4, (2021), 76. https://doi.org/10.1038/s42005-021-00580-w doi: 10.1038/s42005-021-00580-w
[42]	M. Gonen, D. Ron, U. Weinsberg, A. Wool, Finding a dense-core in jellyfish graphs, Comput. Netw., 52 (2008), 2831–2841. https://doi.org/10.1016/j.comnet.2008.06.005 doi: 10.1016/j.comnet.2008.06.005
[43]	F. Safaei, A. Babaei, M. Moudi, Optimally connected hybrid complex networks with windmill graphs backbone, J. Syst. Sci. Complex., 33 (2020), 903–929. https://doi.org/10.1007/s11424-020-8294-x doi: 10.1007/s11424-020-8294-x
[44]	D. Acemoglu, A. Ozdaglar, A. ParandehGheibi, Spread of (mis) information in social networks, Games Econom. Behav. 70 (2010), 194–227. https://doi.org/10.1016/j.geb.2010.01.005 doi: 10.1016/j.geb.2010.01.005
[45]	B. Basavanagoud, S. S. Tallur, Further results on degree splitting graph of a graph, Acta Cienc. Indica Math., 33 (2007), 1403–1414.

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)