{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:49:46Z","timestamp":1770493786142,"version":"3.49.0"},"reference-count":56,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T00:00:00Z","timestamp":1687996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"RSF grant","award":["22-29-00979"],"award-info":[{"award-number":["22-29-00979"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Nowadays, graph theory is one of the most exciting fields of mathematics due to the tremendous developments in modern technology, where it is used in many important applications. The orthogonal double cover (ODC) is a branch of graph theory and is considered as a special class of graph decomposition. In this paper, we decompose the complete bipartite graphs Kx,x by caterpillar graphs using the method of ODCs. The article also deals with constructing the ODCs of Kx,x by general symmetric starter vectors of caterpillar graphs such as stars\u2013caterpillar, the disjoint copies of cycles\u2013caterpillars, complete bipartite caterpillar graphs, and the disjoint copies of caterpillar paths. We decompose the complete bipartite graph by the complete bipartite subgraphs and by the disjoint copies of complete bipartite subgraphs using general symmetric starter vectors. The advantage of some of these new results is that they enable us to decompose the giant networks into large groups of small networks with the comprehensive coverage of all parts of the giant network by using the disjoint copies of symmetric starter subgraphs. The use case of applying the described theory for various applications is considered.<\/jats:p>","DOI":"10.3390\/a16070320","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T01:02:41Z","timestamp":1688086961000},"page":"320","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Orthogonal Double Covers and Decompositions of Complete Bipartite Graphs by Caterpillar Graphs"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2009-3905","authenticated-orcid":false,"given":"Ahmed","family":"El-Mesady","sequence":"first","affiliation":[{"name":"Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, Egypt"}]},{"given":"Tasneem","family":"Farahat","sequence":"additional","affiliation":[{"name":"Faculty of Systems and Computer Engineering, Al-Azhar University, Cairo 11511, Egypt"}]},{"given":"Ramadan","family":"El-Shanawany","sequence":"additional","affiliation":[{"name":"Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, Egypt"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9410-9431","authenticated-orcid":false,"given":"Aleksandr Y.","family":"Romanov","sequence":"additional","affiliation":[{"name":"HSE University, 101000 Moscow, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1007\/s11831-020-09418-0","article-title":"UAV Communication Networks Issues: A Review","volume":"28","author":"Nawaz","year":"2022","journal-title":"Arch. Comput. Methods Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s40519-021-01172-x","article-title":"Brain networks in eating disorders: A systematic review of graph theory studies","volume":"27","author":"Collantoni","year":"2022","journal-title":"Eat. Weight Disord."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1038\/s41562-020-0898-6","article-title":"Social network-based distancing strategies to flatten the COVID-19 curve in a post-lockdown world","volume":"4","author":"Block","year":"2020","journal-title":"Nat. Hum. Behav."},{"key":"ref_4","unstructured":"Merrifield, R.E., and Simmons, H.E. (1989). Topological Methods in Chemistry, Wiley-Interscience."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(73)90067-8","article-title":"The number of caterpillars","volume":"6","author":"Harary","year":"1973","journal-title":"Discret. Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.dam.2011.10.024","article-title":"Maximal independent sets in caterpillar graphs","volume":"160","author":"Ortiz","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_7","unstructured":"Boesch, F.T., Chen, S., and McHugh, J.A.M. (1974). Graphs and Combinatorics. Lecture Notes in Mathematics, Springer."},{"key":"ref_8","first-page":"718","article-title":"Edge irregular reflexive labeling for star, double star and caterpillar graphs","volume":"10","author":"Ibrahim","year":"2020","journal-title":"TWMS J. App. Eng. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"7282245","DOI":"10.1155\/2021\/7282245","article-title":"On Fault-Tolerant Partition Dimension of Homogeneous Caterpillar Graphs","volume":"2021","author":"Azhar","year":"2021","journal-title":"Math. Probl. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01205666","article-title":"Applications of caterpillar trees in chemistry and physics","volume":"1","year":"1987","journal-title":"J. Math. Chem."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF00554539","article-title":"Topological properties of benzenoid systems\u2014An identity for the sextet polynomial","volume":"45","author":"Gutman","year":"1977","journal-title":"Theor. Chim. Acta"},{"key":"ref_12","first-page":"61","article-title":"Spectra and Randic Spectra of Caterpillar Graphs and Applications to the Energy","volume":"77","author":"Andrade","year":"2017","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_13","unstructured":"El-Basil, S. (2005). Advances in the Theory of Benzenoid Hydrocarbons, Springer."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1134\/S0001434622010333","article-title":"Perfect Domination Polynomial of Homogeneous Caterpillar Graphs and of Full Binary Trees","volume":"111","author":"Yimer","year":"2022","journal-title":"Math. Notes"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2018.04.019","article-title":"Leaf realization problem, caterpillar graphs and prefix normal words","volume":"732","author":"Goupil","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","unstructured":"Dinneen, M.J., and Khosravani, M. (2010). Structural Information and Communication Complexity. SIROCCO 2010. Lecture Notes in Computer Science, Springer."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Saraswathi, M., and Meera, K.N. (2021, January 16\u201317). Radio Mean Labeled Graphs to Generate Keys in Cryptography. Proceedings of the 2021 2nd International Conference on Communication, Computing and Industry 4.0 (C2I4), Bangalore, India.","DOI":"10.1109\/C2I454156.2021.9689270"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Schneider, K., Bhagyanath, A., and Roob, J. (2022, January 14). Code generation criteria for buffered exposed datapath architectures from dataflow graphs. Proceedings of the 23rd ACM SIGPLAN\/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems, San Diego, CA, USA.","DOI":"10.1145\/3519941.3535076"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Jegan, R., Vijayakumar, P., and Thirusangu, K. (2022, January 8). A Coding Algorithm using Super-edge Magic Total Labeling of Extended Duplicate Graphs. Proceedings of the 2022 Second International Conference on Computer Science, Engineering and Applications (ICCSEA), Gunupur, India.","DOI":"10.1109\/ICCSEA54677.2022.9936251"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"93375","DOI":"10.1109\/ACCESS.2019.2927244","article-title":"Computing Edge-Weight Bounds of Antimagic Labeling on a Class of Trees","volume":"7","author":"Liu","year":"2019","journal-title":"IEEE Access"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Yao, B., Wang, H., Su, J., and Zhang, W. (2021, January 12\u201314). Graph-Based Lattices Cryptosystem As New Technique of Post-Quantum Cryptography. Proceedings of the 2021 IEEE 5th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, China.","DOI":"10.1109\/IAEAC50856.2021.9390858"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0166-218X(03)00269-5","article-title":"Orthogonal Double Covers of Kn,n by Small Graphs","volume":"138","author":"Gronau","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"El-Mesady, A., Romanov, A.Y., Amerikanov, A.A., and Ivannikov, A.D. (2023). On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing. Algorithms, 16.","DOI":"10.3390\/a16010010"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Colbourn, C.J., Dinitz, J.H., Ii, L.C., Jajcay, R., and Magliveras, S.S. (1996). The CRC Handbook of Combinatorial Designs, CRC Press.","DOI":"10.1201\/9781420049954"},{"key":"ref_25","first-page":"349","article-title":"On Cyclic Decompositions of the Complete Graph into (4m + 2)\u2014Gons","volume":"16","author":"Rosa","year":"1966","journal-title":"Mat. Fyzik\u00e1lny \u010casopis"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.disc.2006.11.050","article-title":"Directed complete bipartite graph decompositions: Indirect constructions","volume":"308","author":"Dukes","year":"2008","journal-title":"Discrete Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0166-218X(03)00274-9","article-title":"Orthogonal double covers of general graphs","volume":"138","author":"Hartmann","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"ref_28","unstructured":"Higazy, M. (2006). A Study on the Orthogonal Double Covers of the Complete Bipartite Graphs. [Master\u2019s Thesis, Menoufia University]."},{"key":"ref_29","unstructured":"Higazy, M. (2009). A Study of the Suborthogonal Double Covers of Complete Bipartite Graphs. [Ph.D. Thesis, Menoufia University]."},{"key":"ref_30","unstructured":"Demetrovics, J., and Katona, G.O.H. (1981). Fundamentals of Combinatorics of Computation Theory, Springer."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.sysarc.2016.04.011","article-title":"NoC routing protocols\u2014Objective-based classification","volume":"66\u201367","author":"Gabis","year":"2016","journal-title":"J. Syst. Archit."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Romanov, A., Myachin, N., and Sukhov, A. (2021, January 13\u201316). Fault-Tolerant Routing in Networks-on-Chip Using Self-Organizing Routing Algorithms. Proceedings of the IECON 2021\u201447th Annual Conference of the IEEE Industrial Electronics Society, Toronto, ON, Canada.","DOI":"10.1109\/IECON48115.2021.9589829"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1023\/A:1016546402248","article-title":"On orthogonal double covers of graphs","volume":"27","author":"Gronau","year":"2002","journal-title":"Des. Codes Cryptogr."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"El-Shanawany, R., Shabana, H., and El-Mesady, A. (2014). On Orthogonal Double Covers of Graphs by Graph-Path and Graph-Cycle, LAP Lambert Academic Publishing.","DOI":"10.9734\/BJMCS\/2014\/5999"},{"key":"ref_35","first-page":"78","article-title":"On the one edge algorithm for the orthogonal double covers","volume":"45","year":"2019","journal-title":"Prikl. Diskretn. Mat."},{"key":"ref_36","first-page":"1","article-title":"A note on orthogonal double covers of complete bipartite graphs by a special class of six caterpillars","volume":"7","author":"Higazy","year":"2010","journal-title":"AKCE J. Graphs Comb."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Higazy, M., El-Mesady, A., and Mohamed, M.S. (2020). On Graph-Orthogonal Arrays by Mutually Orthogonal Graph Squares. Symmetry, 12.","DOI":"10.3390\/sym12111895"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"7349","DOI":"10.3934\/math.2022410","article-title":"A Novel Application on Mutually Orthogonal Graph Squares and Graph-Orthogonal Arrays","volume":"7","author":"Hamed","year":"2022","journal-title":"AIMS Math."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Akavia, A., LaVigne, R., and Moran, T. (2017, January 20\u201324). Topology-hiding computation on all graphs. Proceedings of the Advances in Cryptology\u2013CRYPTO 2017\u201337th Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-319-63688-7_15"},{"key":"ref_40","first-page":"44","article-title":"Topological spaces associated with simple graphs","volume":"9","author":"Kilicman","year":"2018","journal-title":"J. Math. Anal."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"5125","DOI":"10.3233\/JIFS-171561","article-title":"New types of graphs induced by topological spaces","volume":"36","author":"Kozae","year":"2019","journal-title":"J. Intell. Fuzzy Syst."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"El-Mesady, A., and Bazighifan, O. (2022). Construction of Mutually Orthogonal Graph Squares Using Novel Product Techniques. J. Math., 9722983.","DOI":"10.1155\/2022\/9722983"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s40314-022-01987-z","article-title":"Competition Graphs under Interval-Valued m-Polar Fuzzy Environment and Its Application","volume":"41","author":"Mahapatra","year":"2022","journal-title":"Comput. Appl. Math."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Pramanik, T., Muhiuddin, G., Alanazi, A.M., and Pal, M. (2020). An Extension of Fuzzy Competition Graph and Its Uses in Manufacturing Industries. Mathematics, 8.","DOI":"10.3390\/math8061008"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"371","DOI":"10.3233\/IFS-151762","article-title":"Product Vague Graphs and Its Applications","volume":"30","author":"Rashmanlou","year":"2016","journal-title":"J. Intell. Fuzzy Syst."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0012-365X(00)00192-8","article-title":"Edge-disjoint spanners of complete bipartite graphs","volume":"234","author":"Laforest","year":"2001","journal-title":"Discret. Math."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1016\/j.future.2017.08.009","article-title":"AGRA: AI-augmented geographic routing approach for IoT-based incident-supporting applications","volume":"92","author":"Chemodanov","year":"2019","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_48","first-page":"73","article-title":"Broadcasting in small-world communication networks","volume":"85","author":"Comellas","year":"2002","journal-title":"Sirocco"},{"key":"ref_49","unstructured":"Li, W., Zhang, Y., Qiao, M., Chang, L., Qin, L., and Lin, X. (2002, January 18\u201323). Scaling distance labeling on small-world networks. Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, USA."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Carloni, L.P., Pande, P., and Xie, Y. (2009, January 10\u201313). Networks-on-chip in emerging interconnect paradigms: Advantages and challenges. Proceedings of the 2009 3rd ACM\/IEEE International Symposium on Networks-on-Chip, La Jolla, CA, USA.","DOI":"10.1109\/NOCS.2009.5071456"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Richardson, T.D., Nicopoulos, C., Park, D., Narayanan, V., Xie, Y., Das, C., and Degalahal, V. (2006, January 3\u20137). A hybrid SoC interconnect with dynamic TDMA-based transaction-less buses and on-chip networks. Proceedings of the 19th International Conference on VLSI Design Held Jointly with 5th International Conference on Embedded Systems Design (VLSID\u201906), Hyderabad, India.","DOI":"10.1109\/VLSID.2006.10"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Batra, N., and Singh, B. (2022, January 23\u201325). Evolution of Efficient On-Chip Interconnect Architecture for SOC: A Review. Proceedings of the 2022 IEEE Global Conference on Computing, Power and Communication Technologies (GlobConPT), New Delhi, India.","DOI":"10.1109\/GlobConPT57482.2022.9938209"},{"key":"ref_53","unstructured":"Conti, M. (2022). Applications in Electronics Pervading Industry, Environment and Society. ApplePies 2021. Lecture Notes in Electrical Engineering, Springer."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"103175","DOI":"10.1016\/j.micpro.2020.103175","article-title":"Task mapping and flow priority assignment of real-time industrial applications for network-on-chip based design","volume":"77","author":"Khare","year":"2020","journal-title":"Microprocess Microsyst."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Romanov, A.Y., Myachin, N.M., Lezhnev, E.V., Ivannikov, A.D., and El-Mesady, A. (2023). Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip. Micromachines, 14.","DOI":"10.3390\/mi14010141"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"e6055","DOI":"10.1002\/cpe.6055","article-title":"A high-performance FPGA-based multicrossbar prioritized network-on-chip","volume":"33","author":"Alaei","year":"2021","journal-title":"Concurr. Comput. Pract. Exp."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/7\/320\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:03:50Z","timestamp":1760126630000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/7\/320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,29]]},"references-count":56,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["a16070320"],"URL":"https:\/\/doi.org\/10.3390\/a16070320","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,29]]}}}