{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T15:48:50Z","timestamp":1740152930448,"version":"3.37.3"},"reference-count":45,"publisher":"American Institute of Mathematical Sciences (AIMS)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["NHM"],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:p xml:lang=\"fr\">&lt;abstract&gt;&lt;p&gt;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.&lt;\/p&gt;&lt;\/abstract&gt;<\/jats:p>","DOI":"10.3934\/nhm.2023075","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T11:41:31Z","timestamp":1697197291000},"page":"1713-1746","source":"Crossref","is-referenced-by-count":0,"title":["Optimal secret share distribution in degree splitting communication networks"],"prefix":"10.3934","volume":"18","author":[{"given":"Ra\u00fal M.","family":"Falc\u00f3n","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics I, University of Seville, Avda. Reina Mercedes 4A, Seville, 41012, Spain"}]},{"given":"Venkitachalam","family":"Aparna","sequence":"additional","affiliation":[{"name":"PG and Research Department of Mathematics, Kongunadu Arts and Science College, GN Mills, Tamil Nadu, 641 029, Coimbatore, India"}]},{"given":"Nagaraj","family":"Mohanapriya","sequence":"additional","affiliation":[{"name":"PG and Research Department of Mathematics, Kongunadu Arts and Science College, GN Mills, Tamil Nadu, 641 029, Coimbatore, India"}]}],"member":"2321","reference":[{"key":"key-10.3934\/nhm.2023075-1","doi-asserted-by":"publisher","unstructured":"G. R. Blakley, Safeguarding cryptographic keys, <i>Managing Requirements Knowledge, International Workshop on. IEEE Computer Society<\/i>, (1979), 313\u2013317. https:\/\/doi.org\/10.1109\/MARK.1979.8817296","DOI":"10.1109\/MARK.1979.8817296"},{"key":"key-10.3934\/nhm.2023075-2","doi-asserted-by":"publisher","unstructured":"A. Shamir, How to share a secret, <i>Comm. ACM<\/i>, <b>22<\/b> (1979), 612\u2013613. https:\/\/doi.org\/10.1145\/359168.359176","DOI":"10.1145\/359168.359176"},{"key":"key-10.3934\/nhm.2023075-3","doi-asserted-by":"publisher","unstructured":"V. Attasena, J. Darmont, N. Harbi, Secret sharing for cloud data security, <i>VLDB J.<\/i>, <b>26<\/b> (2017), 657\u2013681. https:\/\/doi.org\/10.1007\/s00778-017-0470-9","DOI":"10.1007\/s00778-017-0470-9"},{"key":"key-10.3934\/nhm.2023075-4","doi-asserted-by":"publisher","unstructured":"L. Ogiela, M. R. Ogiela, H. Ko, Intelligent data management and security in cloud computing. <i>Sensors<\/i>, <b>20<\/b> (2020), 3458. https:\/\/doi.org\/10.3390\/s20123458","DOI":"10.3390\/s20123458"},{"key":"key-10.3934\/nhm.2023075-5","doi-asserted-by":"crossref","unstructured":"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: <i>Proceedings of the International Conference on High Performance Computing, Networking, Storage, and Analysis (SC'16)<\/i>, IEEE, Los Alamitos, CA, (2016), 347\u2013358. <ext-link ext-link-type=\"uri\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/doi.org\/10.1109\/SC.2016.29\">https:\/\/doi.org\/10.1109\/SC.2016.29<\/ext-link>","DOI":"10.1109\/SC.2016.29"},{"key":"key-10.3934\/nhm.2023075-6","doi-asserted-by":"publisher","unstructured":"Q. Y. Hu, C. Wen, T. Z. Huang, Z. L. Shen, X. M. Gu, A variant of the Power-Arnoldi algorithm for computing PageRank, <i>J. Comput. Appl. Math.<\/i>, <b>381<\/b> (2021), 113034. https:\/\/doi.org\/10.1016\/j.cam.2020.113034","DOI":"10.1016\/j.cam.2020.113034"},{"key":"key-10.3934\/nhm.2023075-7","doi-asserted-by":"publisher","unstructured":"M. E. Coimbra, A. P. Francisco, L. Veiga, An analysis of the graph processing landscape, <i>J. Big Data<\/i>, <b>8<\/b> (2021), 55. https:\/\/doi.org\/10.1186\/s40537-021-00443-9","DOI":"10.1186\/s40537-021-00443-9"},{"key":"key-10.3934\/nhm.2023075-8","doi-asserted-by":"publisher","unstructured":"Z. Tuza, Graph colorings with local constraints\u2014a survey, <i>Discuss. Math. Graph Theory<\/i>, <b>17<\/b> (1997), 161\u2013228. https:\/\/doi.org\/10.7151\/dmgt.1049","DOI":"10.7151\/dmgt.1049"},{"key":"key-10.3934\/nhm.2023075-9","doi-asserted-by":"publisher","unstructured":"P. Formanowicz, K. Tana\u015b, A survey of graph coloring - its types, methods and applications, <i>Found. Comput. Decision Sci.<\/i>, <b>37<\/b> (2012), 223\u2013238. https:\/\/doi.org\/10.2478\/v10209-011-0012-y","DOI":"10.2478\/v10209-011-0012-y"},{"key":"key-10.3934\/nhm.2023075-10","unstructured":"R. M. R. Lewis, <i>Guide to graph colouring\u2014algorithms and applications<\/i>, Cham: Springer, (2021). <ext-link ext-link-type=\"uri\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/doi.org\/10.1007\/978-3-030-81054-2\">https:\/\/doi.org\/10.1007\/978-3-030-81054-2<\/ext-link>"},{"key":"key-10.3934\/nhm.2023075-11","doi-asserted-by":"publisher","unstructured":"S. Labed, A. Kout, S. Chikhi, Solving the graph $b$-coloring problem with hybrid genetic algorithm, <i>3rd International Conference on Pattern Analysis and Intelligent Systems (PAIS 2018)<\/i>, (2018), 1\u20137. https:\/\/doi.org\/10.1109\/PAIS.2018.8598525","DOI":"10.1109\/PAIS.2018.8598525"},{"key":"key-10.3934\/nhm.2023075-12","doi-asserted-by":"publisher","unstructured":"E. F. Olariu, C. Fr\u0103sinaru, Improving lower bounds for equitable chromatic number, <i>Comput. Oper. Res.<\/i>, <b>143<\/b> (2022), 105790. https:\/\/doi.org\/10.1016\/j.cor.2022.105790","DOI":"10.1016\/j.cor.2022.105790"},{"key":"key-10.3934\/nhm.2023075-13","doi-asserted-by":"publisher","unstructured":"Y. Imine, H. Lakhlef, M. Raynal, F. Ta\u00efani, DMCSC: a fully distributed multi-coloring approach for scalable communication in synchronous broadcast networks, <i>J. Supercomput.<\/i>, <b>79<\/b> (2023), 788\u2013813. https:\/\/doi.org\/10.1007\/s11227-022-04700-3","DOI":"10.1007\/s11227-022-04700-3"},{"key":"key-10.3934\/nhm.2023075-14","doi-asserted-by":"publisher","unstructured":"Y. Shang, Concentration of rainbow $k$-connectivity of a multiplex random graph, <i>Theoret. Comput. Sci.<\/i>, <b>951<\/b> (2023), 113771. https:\/\/doi.org\/10.1016\/j.tcs.2023.113771","DOI":"10.1016\/j.tcs.2023.113771"},{"key":"key-10.3934\/nhm.2023075-15","doi-asserted-by":"publisher","unstructured":"S. Roy, A. S. Sairam, Distributed star coloring of network for IP traceback, <i>Int. J. Inf. Secur.<\/i>, <b>17<\/b> (2018), 315\u2013326. https:\/\/doi.org\/10.1007\/s10207-017-0366-0","DOI":"10.1007\/s10207-017-0366-0"},{"key":"key-10.3934\/nhm.2023075-16","doi-asserted-by":"publisher","unstructured":"R. M. Falc\u00f3n, N. Mohanapriya, V. Aparna, Optimal shadow allocations of secret sharing schemes arisen from the dynamic coloring of extended neighborhood coronas, <i>Mathematics<\/i>, <b>10<\/b> (2022), 2018. https:\/\/doi.org\/10.3390\/math10122018","DOI":"10.3390\/math10122018"},{"key":"key-10.3934\/nhm.2023075-17","unstructured":"B. Montgomery, Dynamic Goloring of Graphs, Doctoral Thesis of West Virginia University, Morgantown, 2001."},{"key":"key-10.3934\/nhm.2023075-18","doi-asserted-by":"publisher","unstructured":"X. Li, X. Yao, W. Zhou, H. Broersma, Complexity of conditional colorability of graphs, <i>Appl. Math. Lett.<\/i>, <b>22<\/b> (2009), 320\u2013324. https:\/\/doi.org\/10.1016\/j.aml.2008.04.003","DOI":"10.1016\/j.aml.2008.04.003"},{"key":"key-10.3934\/nhm.2023075-19","doi-asserted-by":"publisher","unstructured":"A. S. Akbari, A. Dehghana, M. Ghanbari, On the difference between chromatic and dynamic chromatic number of graphs, <i>Discrete Math.<\/i>, <b>312<\/b> (2012), 2579\u20132583. https:\/\/doi.org\/10.1016\/j.disc.2011.09.006","DOI":"10.1016\/j.disc.2011.09.006"},{"key":"key-10.3934\/nhm.2023075-20","doi-asserted-by":"publisher","unstructured":"M. Alishahi, Dynamic chromatic number of regular graphs, <i>Discrete Appl. Math.<\/i>, <b>160<\/b> (2012), 2098\u20132103. https:\/\/doi.org\/10.1016\/j.dam.2012.05.017","DOI":"10.1016\/j.dam.2012.05.017"},{"key":"key-10.3934\/nhm.2023075-21","doi-asserted-by":"publisher","unstructured":"V. Aparna, N. Mohanapriya, On $r$-dynamic coloring of some graphs, <i>Kong. Res. J.<\/i>, <b>7<\/b> (2020), 82\u201387. https:\/\/doi.org\/10.26524\/krj.2020.13","DOI":"10.26524\/krj.2020.13"},{"key":"key-10.3934\/nhm.2023075-22","doi-asserted-by":"publisher","unstructured":"T. Deepa, R. M. Falc\u00f3n, M. Venkatachalam, On the $r$-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph, <i>AIMS Math<\/i>, <b>6<\/b> (2021), 1470\u20131496. https:\/\/doi.org\/10.3934\/math.2021090","DOI":"10.3934\/math.2021090"},{"key":"key-10.3934\/nhm.2023075-23","doi-asserted-by":"publisher","unstructured":"R. M. Falc\u00f3n, S. Gowri, M. Venkatachalam, Solving the dynamic coloring problem for direct products of paths with fan graphs, <i>Analele Stiintifice ale Univ. Ovidius Constanta, Ser. Mat.<\/i>, <b>31<\/b> (2023), 115\u2013142. https:\/\/doi.org\/10.2478\/auom-2023-0006","DOI":"10.2478\/auom-2023-0006"},{"key":"key-10.3934\/nhm.2023075-24","doi-asserted-by":"publisher","unstructured":"K. Kaliraj, H. Naresh, Kumar, J. Vernold Vivin, On dynamic colouring of Cartesian product of complete graph with some graphs, <i>J. Taibah Univ. Sci.<\/i>, <b>14<\/b> (2020), 168\u2013171. https:\/\/doi.org\/10.1080\/16583655.2020.1713586","DOI":"10.1080\/16583655.2020.1713586"},{"key":"key-10.3934\/nhm.2023075-25","unstructured":"H. J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, <i>Ars Combin.<\/i>, <b>68<\/b> (2003), 193\u2013201."},{"key":"key-10.3934\/nhm.2023075-26","doi-asserted-by":"publisher","unstructured":"H. J. Lai, B. Montgomery, Z. Tao, Conditional colorings of graphs, <i>Discrete Math.<\/i>, <b>306<\/b> (2006), 1997\u20132004. https:\/\/doi.org\/10.1016\/j.disc.2006.03.052","DOI":"10.1016\/j.disc.2006.03.052"},{"key":"key-10.3934\/nhm.2023075-27","doi-asserted-by":"publisher","unstructured":"J. Vernold Vivin, N. Mohanapriya, J. Kok, M. Venkatachalam, On dynamic coloring of certain cycle-related graphs, <i>Arab. J. Math.<\/i>, <b>9<\/b> (2020), 213\u2013221. https:\/\/doi.org\/10.1007\/s40065-018-0219-3","DOI":"10.1007\/s40065-018-0219-3"},{"key":"key-10.3934\/nhm.2023075-28","doi-asserted-by":"publisher","unstructured":"G. Nandini, M. Venkatachalam, R. M. Falc\u00f3n, On the $r$-dynamic coloring of subdivision-edge coronas of a path, <i>AIMS Math<\/i>, <b>5<\/b> (2020), 4546\u20134562. https:\/\/doi.org\/10.3934\/math.2020292","DOI":"10.3934\/math.2020292"},{"key":"key-10.3934\/nhm.2023075-29","doi-asserted-by":"publisher","unstructured":"J. V. Vivin, N. Mohanapriya, J. Kok, M. Venkatachalam, On dynamic coloring of certain cycle-related graphs, <i>Arab. J. Math.<\/i>, <b>9<\/b> (2020), 213\u2013221. https:\/\/doi.org\/10.1007\/s40065-018-0219-3","DOI":"10.1007\/s40065-018-0219-3"},{"key":"key-10.3934\/nhm.2023075-30","doi-asserted-by":"publisher","unstructured":"T. Deepa, M. Venkatachalam, Dafik, On $r$-dynamic coloring of the gear graph families, <i>Proyecciones<\/i>, <b>40<\/b> (2021), 1\u201315. http:\/\/dx.doi.org\/10.22199\/issn.0717-6279-2021-01-0001","DOI":"10.22199\/issn.0717-6279-2021-01-0001"},{"key":"key-10.3934\/nhm.2023075-31","doi-asserted-by":"publisher","unstructured":"R. M. Falc\u00f3n, M. Venkatachalam, S. Gowri, G. Nandini, On the $r$-dynamic coloring of some fan graph families, <i>Analele Stiintifice ale Univ. Ovidius Constanta, Ser. Mat.<\/i>, <b>29<\/b> (2021), 151\u2013181. https:\/\/doi.org\/10.2478\/auom-2021-0039","DOI":"10.2478\/auom-2021-0039"},{"key":"key-10.3934\/nhm.2023075-32","doi-asserted-by":"publisher","unstructured":"K. Kalaiselvi, N. Mohanapriya, V. Aparna, $r$-Dynamic chromatic number of subdivision-edge neighborhood corona of certain graph families, <i>Discrete Math. Algorithms Appl.<\/i>, (2023), 2350026. https:\/\/doi.org\/10.1142\/S179383092350026X","DOI":"10.1142\/S179383092350026X"},{"key":"key-10.3934\/nhm.2023075-33","doi-asserted-by":"publisher","unstructured":"G. Nandini, M. Venkatachalam, J. Vernold Vivin, On $r$-dynamic coloring of $n$-sunlet graph families, <i>Proc. Jangjeon Math. Soc.<\/i>, <b>26<\/b> (2023), 23\u201342. http:\/\/dx.doi.org\/10.17777\/pjms2023.26.1.23","DOI":"10.17777\/pjms2023.26.1.23"},{"key":"key-10.3934\/nhm.2023075-34","doi-asserted-by":"publisher","unstructured":"Y. Chen, S. Fan, H. J. Lai, M. Xu, Graph $r$-hued colorings\u2013A survey, <i>Discret. Appl. Math.<\/i>, <b>321<\/b> (2022), 24\u201348. https:\/\/doi.org\/10.1016\/j.dam.2022.06.003","DOI":"10.1016\/j.dam.2022.06.003"},{"key":"key-10.3934\/nhm.2023075-35","doi-asserted-by":"publisher","unstructured":"J. Kim, S. Ok, Dynamic choosability of triangle-free graphs and sparse random graphs, <i>J. Graph Theory<\/i>, <b>87<\/b>, (2017), 347\u2013355. https:\/\/doi.org\/10.1002\/jgt.22161","DOI":"10.1002\/jgt.22161"},{"key":"key-10.3934\/nhm.2023075-36","unstructured":"R. Ponraj, S. Somasundaram, On the degree splitting graph of a graph, <i>Natl. Acad. Sci. Lett.<\/i>, <b>27<\/b> (2004), 275\u2013278."},{"key":"key-10.3934\/nhm.2023075-37","doi-asserted-by":"crossref","unstructured":"F. Harary, <i>Graph Theory<\/i>, Boulder: Westview Press, 1969.","DOI":"10.21236\/AD0705364"},{"key":"key-10.3934\/nhm.2023075-38","doi-asserted-by":"publisher","unstructured":"K. D. Mackenzie, Decomposition of communication networks, <i>J Math Psychol<\/i>, <b>4<\/b> (1967), 162\u2013174. https:\/\/doi.org\/10.1016\/0022-2496(67)90048-X","DOI":"10.1016\/0022-2496(67)90048-X"},{"key":"key-10.3934\/nhm.2023075-39","doi-asserted-by":"publisher","unstructured":"D. Angel, I. A. Arputhamary, R. Revathi, M. Nirmala, Secure node covering of cocktail party graphs and generalized fan graphs. <i>2022 Third International Conference on Intelligent Computing Instrumentation and Control Technologies (ICICICT)<\/i>, (2022), 261\u2013264. https:\/\/doi.org\/10.1109\/ICICICT54557.2022.9918002","DOI":"10.1109\/ICICICT54557.2022.9918002"},{"key":"key-10.3934\/nhm.2023075-40","doi-asserted-by":"publisher","unstructured":"B. Basavanagoud, P. Jakkannavar, Praveen, S. Policepatil, Integrity of total transformation graphs, <i>Electron. J. Graph Theory Appl.<\/i>, <b>9<\/b> (2021), 309\u2013329. https:\/\/doi.org\/10.5614\/ejgta.2021.9.2.6","DOI":"10.5614\/ejgta.2021.9.2.6"},{"key":"key-10.3934\/nhm.2023075-41","doi-asserted-by":"publisher","unstructured":"A. Bassolas, V. Nicosia, First-passage times to quantify and compare structural correlations and heterogeneity in complex systems, <i>Commun. Phys.<\/i>, <b>4<\/b>, (2021), 76. https:\/\/doi.org\/10.1038\/s42005-021-00580-w","DOI":"10.1038\/s42005-021-00580-w"},{"key":"key-10.3934\/nhm.2023075-42","doi-asserted-by":"publisher","unstructured":"M. Gonen, D. Ron, U. Weinsberg, A. Wool, Finding a dense-core in jellyfish graphs, <i>Comput. Netw.<\/i>, <b>52<\/b> (2008), 2831\u20132841. https:\/\/doi.org\/10.1016\/j.comnet.2008.06.005","DOI":"10.1016\/j.comnet.2008.06.005"},{"key":"key-10.3934\/nhm.2023075-43","doi-asserted-by":"publisher","unstructured":"F. Safaei, A. Babaei, M. Moudi, Optimally connected hybrid complex networks with windmill graphs backbone, <i>J. Syst. Sci. Complex.<\/i>, <b>33<\/b> (2020), 903\u2013929. https:\/\/doi.org\/10.1007\/s11424-020-8294-x","DOI":"10.1007\/s11424-020-8294-x"},{"key":"key-10.3934\/nhm.2023075-44","doi-asserted-by":"publisher","unstructured":"D. Acemoglu, A. Ozdaglar, A. ParandehGheibi, Spread of (mis) information in social networks, <i>Games Econom. Behav.<\/i> <b>70<\/b> (2010), 194\u2013227. https:\/\/doi.org\/10.1016\/j.geb.2010.01.005","DOI":"10.1016\/j.geb.2010.01.005"},{"key":"key-10.3934\/nhm.2023075-45","unstructured":"B. Basavanagoud, S. S. Tallur, Further results on degree splitting graph of a graph, <i>Acta Cienc. Indica Math.<\/i>, <b>33<\/b> (2007), 1403\u20131414."}],"container-title":["Networks and Heterogeneous Media"],"original-title":[],"link":[{"URL":"http:\/\/www.aimspress.com\/article\/doi\/10.3934\/nhm.2023075?viewType=html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T11:42:09Z","timestamp":1697197329000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.aimspress.com\/article\/doi\/10.3934\/nhm.2023075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.3934\/nhm.2023075","relation":{},"ISSN":["1556-1801"],"issn-type":[{"type":"print","value":"1556-1801"}],"subject":[],"published":{"date-parts":[[2023]]}}}