Partially balanced network designs and graph codes generation

A. El-Mesady; Y. S. Hamed; M. S. Mohamed; H. Shabana; A. El-Mesady; Y. S. Hamed; M. S. Mohamed; H. Shabana

doi:10.3934/math.2022135

AIMS Mathematics

2022, Volume 7, Issue 2: 2393-2412. doi: 10.3934/math.2022135

Previous Article Next Article

Research article

Partially balanced network designs and graph codes generation

1.
Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, Egypt
2.
Department of Mathematics and Statistics, College of Science, Taif University, P.O. Box 11099, Taif 21944, Saudi Arabia

Received: 23 June 2021 Accepted: 28 October 2021 Published: 12 November 2021
MSC : 05B30, 0570, 94A60, 94A62

Partial balanced incomplete block designs have a wide range of applications in many areas. Such designs provide advantages over fully balanced incomplete block designs as they allow for designs with a low number of blocks and different associations. This paper introduces a class of partially balanced incomplete designs. We call it partially balanced network designs (PBNDs). The fundamentals and properties of PBNDs are studied. We are concerned with modeling PBNDs as graph designs. Some direct constructions of small PBNDs and generalized PBNDs are introduced. Besides that, we show that our modeling yields an effective utilization of PNBDs in constructing graph codes. Here, we are interested in constructing graph codes from bipartite graphs. We have proved that these codes have good characteristics for error detection and correction. In the end, the paper introduces a novel technique for generating new codes from already constructed codes. This technique results in increasing the ability to correct errors.
- balanced incomplete block design,
- group divisible designs,
- networks designs,
- Cartesian product,
- Abelian groups,
- error detection and correction
Citation: A. El-Mesady, Y. S. Hamed, M. S. Mohamed, H. Shabana. Partially balanced network designs and graph codes generation[J]. AIMS Mathematics, 2022, 7(2): 2393-2412. doi: 10.3934/math.2022135

Related Papers:

Abstract

Partial balanced incomplete block designs have a wide range of applications in many areas. Such designs provide advantages over fully balanced incomplete block designs as they allow for designs with a low number of blocks and different associations. This paper introduces a class of partially balanced incomplete designs. We call it partially balanced network designs (PBNDs). The fundamentals and properties of PBNDs are studied. We are concerned with modeling PBNDs as graph designs. Some direct constructions of small PBNDs and generalized PBNDs are introduced. Besides that, we show that our modeling yields an effective utilization of PNBDs in constructing graph codes. Here, we are interested in constructing graph codes from bipartite graphs. We have proved that these codes have good characteristics for error detection and correction. In the end, the paper introduces a novel technique for generating new codes from already constructed codes. This technique results in increasing the ability to correct errors.

References

[1]	J. A. Bondy, U. S. R. Murty, Graph theory with applications, Elsevier Science Publishing Co., Inc., New York, USA, 1976. doi: 10.1057/jors.1977.45.
[2]	J. A. Bondy, U. S. R. Murty, Graph theory, Springer, Berlin, 2008.
[3]	D. R. Stinson, Combinatorial designs: Constructions and analysis, Springer, New York, 2004.
[4]	R. Khattree, On construction of constant block-sum partially balanced incomplete block designs, Commun. Stat. Theor. M., 49 (2020), 2585-2606. doi: 10.1080/03610926.2019.1576895. doi: 10.1080/03610926.2019.1576895
[5]	P. Kaur, D. G. Kumar, Construction of incomplete Sudoku square and partially balanced incomplete block designs, Commun. Stat. Theor. M., 49 (2020), 1462-1474. doi: 10.1080/03610926.2018.1563177. doi: 10.1080/03610926.2018.1563177
[6]	I. Iqbal, M. Parveen, Z. Mahmood, New diallel cross designs through resolvable balanced incomplete block designs for field experiments, Sarhad J. Agric., 34 (2018), 994-1000. doi: 10.17582/journal.sja/2018/34.4.994.1000. doi: 10.17582/journal.sja/2018/34.4.994.1000
[7]	A. Adhikari, M. Bose, D. Kumar, B. Roy, Applications of partially balanced incomplete block designs in developing (2, n)-visual cryptographic schemes, IEICE T. Fund. Electr., E90-A (2007), 949-951. doi: 10.1093/ietfec/e90-a.5.949. doi: 10.1093/ietfec/e90-a.5.949
[8]	R. C. Bose, Partially balanced incomplete block designs with two associate classes involving only two replications, Calcutta Stat. Assoc. Bul., 3 (1951), 120-125. doi: 10.1177/0008068319510304. doi: 10.1177/0008068319510304
[9]	R. C. Bose, K. R. Nair, Partially balanced incomplete block designs, Sankhya, 4 (1939), 337-372. Available from: https://www.jstor.org/stable/40383923.
[10]	R. C. Bose, T. Shimamoto, Classification and analysis of partially balanced incomplete block designs with two associate classes, J. Am. Stat. Assoc., 47 (1952), 151-184. doi: 10.2307/2280741. doi: 10.2307/2280741
[11]	W. D. Wallis, Regular graph designs, J. Stat. Plan. Infer., 51 (1996), 273-281. doi: 10.1016/0378-3758(95)00091-7. doi: 10.1016/0378-3758(95)00091-7
[12]	D. L. Kreher, G. F. Royle, W. D. Wallis, A family of resolvable regular graph designs, Discrete Math., 156 (1996), 269-275. doi: 10.1016/0012-365X(95)00052-X. doi: 10.1016/0012-365X(95)00052-X
[13]	H. B. Walikar, B. D. Acharya, H. S. Ramane, H. G. Shekharappa, S. Arumugam, Partially balanced incomplete block designs arising from minimal dominating sets of a graph, AKCE. Int. J. Graphs Co., 4 (2007), 223-232. doi: 10.1080/09728600.2007.12088837. doi: 10.1080/09728600.2007.12088837
[14]	F. R. Barandagh, A. R. Barghi, B. Pejman, M. R. Parsa, Strongly regular graphs arising from balanced incomplete block design with λ = 1, Gen. Math. Notes, 24 (2014), 70-77.
[15]	S. A. Cakiroglu, Optimal regular graph designs, Stat. Comput., 28 (2018), 103-112. doi: 10.1007/s11222-016-9720-8. doi: 10.1007/s11222-016-9720-8
[16]	R. Ahmed, F. Shehzad, M. Jamil, H. M. K. Rasheed, Construction of some circular regular graph designs in blocks of size four using cyclic shifts, J. Stat. Theory Appl., 19 (2020), 314-324. doi: 10.2991/jsta.d.200423.001. doi: 10.2991/jsta.d.200423.001
[17]	A. Boua, L. Oukhtite, A. Raji, O. A. Zemzami, An algorithm to construct error correcting codes from planar near-rings, Int. J. Math. Eng. Sci., 3 (2014), 614-623. Available from: https://vixra.org/pdf/1405.0130v1.pdf.
[18]	C. J. Colbourn, J. H. Dinitz, Handbook of combinatorial designs, 2 Eds., Chapman and Hall-CRC, 2007.
[19]	S. J. M. Hwang, Application of balanced incomplete block designs in error detection and correction, 2016. doi: 10.4135/9781473941977.
[20]	R. Merris, Combinatorics, 2 Eds., John Wiley & Sons, Inc., 2003.
[21]	U. Shumacher, Suborthogonal double covers of complete graphs by stars, Discret. Appl. Math., 95 (1999), 439-444. doi: 10.1016/S0166-218X(99)00091-8. doi: 10.1016/S0166-218X(99)00091-8
[22]	S. A Hartmann, Symptotic results on suborthogonal G-decompositions of complete digraphs, Discret. Appl. Math., 95 (1999), 311-320. doi: 10.1016/S0166-218X(99)00083-9. doi: 10.1016/S0166-218X(99)00083-9
[23]	S. Hartmann, U. Shumacher, Suborthogonal double covers of complete graphs, Congressus Numerantium, 147 (2000), 33-40.
[24]	R. El-Shanawany, H. Shabana, General cyclic orthogonal double covers of finite regular circulant graphs, Open J. Discret. Math., 4 (2014), 19-27. doi: 10.4236/ojdm.2014.42004. doi: 10.4236/ojdm.2014.42004
[25]	M. Higazy, Suborthogonal double covers of the complete bipartite graphs by all bipartite subgraphs with five edges over finite fields, Far East J. Appl. Math., 91 (2015), 63-80. doi: 10.17654/FJAMApr2015_063_080. doi: 10.17654/FJAMApr2015_063_080
[26]	H. D. O. F. Gronau, M. Grüttmüller, S. Hartmann, U. Leck, V. Leck, On orthogonal double covers of graphs, Design. Code. Cryptogr., 7 (2002), 49-91. doi: 10.1023/A:1016546402248. doi: 10.1023/A:1016546402248
[27]	R. El-Shanawany, M. Higazy, H. Shabana, A. El-Mesady, Cartesian product of two symmetric starter vectors of orthogonal double covers, AKCE Int. J. Graphs Co., 12 (2015), 59-63. doi: 10.1016/j.akcej.2015.06.009. doi: 10.1016/j.akcej.2015.06.009
[28]	S. El-Serafi, R. El-Shanawany, H. Shabana, Orthogonal double cover of complete bipartite graph by disjoint union of complete bipartite graphs, Ain. Shams Eng. J., 6 (2015), 657-660. doi: 10.1016/j.asej.2014.12.002. doi: 10.1016/j.asej.2014.12.002
[29]	R. El-Shanawany, A. El-Mesady, Cyclic orthogonal double covers of circulants by certain nerve cell graphs, Contrib. Discret. Math., 14 (2019), 105-116. doi: 10.11575/cdm.v14i1.62428. doi: 10.11575/cdm.v14i1.62428
[30]	R. El-Shanawany, A. El-Mesady, On cyclic orthogonal double covers of circulant graphs by special infinite graphs, AKCE Int. J. Graphs Co., 14 (2017), 199-207. doi: 10.1016/j.akcej.2017.04.002. doi: 10.1016/j.akcej.2017.04.002
[31]	R. Sampathkumar, S. Srinivasan, Cyclic orthogonal double covers of 4-regular circulant graphs, Discrete Math., 311 (2011), 2417-2422. doi: 10.1016/j.disc.2011.06.021. doi: 10.1016/j.disc.2011.06.021
[32]	R. El-Shanawany, A. El-Mesady, On the one edge algorithm for the orthogonal double covers, Prikl. Diskretn. Mat., 45 (2019), 78-84. doi: 10.17223/20710410/45/8. doi: 10.17223/20710410/45/8
[33]	R. Sampathkumar, Orthogonal double covers of complete bipartite graphs, Australas. J. Comb., 49 (2011), 15-18. Available from: https://ajc.maths.uq.edu.au/pdf/49/ajc_v49_p015.pdf.
[34]	R. El-Shanawany, H. D. O. F. Gronau, M. Grüttmüller, Orthogonal double covers of K_{n, n} by small graphs, Discret. Appl. Math., 138 (2004), 47-63. doi: 10.1016/S0166-218X(03)00269-5. doi: 10.1016/S0166-218X(03)00269-5
[35]	M. Higazy, R. Scapellato, Y. S. Hamed, A complete classification of 5-regular circulant graphs that allow cyclic orthogonal double covers, J. Algebr. Comb., 2021. doi: 10.1007/s10801-020-01008-4. doi: 10.1007/s10801-020-01008-4
[36]	R. Scapellato, R. El Shanawany, M. Higazy, Orthogonal double covers of Cayley graphs, Discret. Appl. Math, 157 (2009), 3111-3118. doi: 10.1016/j.dam.2009.06.005. doi: 10.1016/j.dam.2009.06.005
[37]	R. Sampathkumar, S. Srinivasan, More mutually orthogonal graph squares, Utilitas Math., 91 (2013), 345-354.
[38]	R. El-Shanawany, A. El-Mesady, Mutually orthogonal graph squares for disjoint union of stars, Ars Comb., 149 (2020), 83-91.
[39]	M. Higazy, Lambda-mutually orthogonal covers of complete bipartite graphs, Adv. Appl. Discret. Mat., 17 (2016), 151-167. doi: 10.17654/DM017020151. doi: 10.17654/DM017020151
[40]	R. El-Shanawany, A. El-Mesady, On mutually orthogonal certain graph squares, Online J. Anal. Comb., 14 (2020).
[41]	R. Sampathkumar, S. Srinivasan, Mutually orthogonal graph squares, J. Comb. Des., 17 (2009), 369-373. doi: 10.1002/jcd.20216. doi: 10.1002/jcd.20216
[42]	R. El-Shanawany, On mutually orthogonal disjoint copies of graph squares, Note Mat., 36 (2016), 89-98. doi: 10.1285/i15900932v36n2p89. doi: 10.1285/i15900932v36n2p89
[43]	M. Higazy, A. El-Mesady, M. S. Mohamed, On graph-orthogonal arrays by mutually orthogonal graph squares, Symmetry, 12 (2020), 1895. doi: 10.3390/sym12111895. doi: 10.3390/sym12111895
[44]	C. J. Colbourn, J. H. Dinitz, Mutually orthogonal latin squares: A brief survey of constructions, J. Stat. Plan. Infer., 95 (2001), 9-48. doi: 10.1016/S0378-3758(00)00276-7. doi: 10.1016/S0378-3758(00)00276-7
[45]	M. Higazy, A. El-Mesady, E. E. Mahmoud, M. H. Alkinani, Circular intensely orthogonal double cover design of balanced complete multipartite graphs, Symmetry, 12 (2020), 1743. doi: 10.3390/sym12101743. doi: 10.3390/sym12101743
[46]	N. Yu. Erokhovets, Gal's conjecture for nestohedra corresponding to complete bipartite graphs, P. Steklov. Math., 266 (2009), 120-132. doi: 10.1134/S0081543809030079. doi: 10.1134/S0081543809030079
[47]	S. Hartmann, Orthogonal decompositions of complete digraphs, Graph. Combinator., 18 (2002), 285-302. doi: 10.1007/s003730200021. doi: 10.1007/s003730200021
[48]	D. Fronček, A. Rosa, Symmetric graph designs on friendship graphs, J. Comb. Des., 8 (2000), 201-206. doi: 10.1002/(sici)1520-6610(2000)8:3<201::aid-jcd5>3.0.co;2-#. doi: 10.1002/(sici)1520-6610(2000)8:3<201::aid-jcd5>3.0.co;2-#
[49]	H. D. O. F. Gronau, R. C. Mullin, A. Rosa, P. J. Schellenberg, Symmetric graph designs, Graph. Combinator., 16 (2000), 93-102. doi: 10.1007/s003730050006. doi: 10.1007/s003730050006
[50]	P. M. Gergely, Partitions with certain intersection properties, J. Comb. Des., 19 (2011), 345-354. doi: 10.1002/jcd.20290. doi: 10.1002/jcd.20290
[51]	Jr. E. Assmus, J. D. Key, Designs and codes: An update, Code. Des. Geom., 9 (1996), 7-27. doi: 10.1007/BF00169770. doi: 10.1007/BF00169770
[52]	A. E. Brouwer, C. A. Eijl, On the p-rank of the adjacency matrices of strongly regular graphs, J. Algebr. Comb., 1 (1992), 329-346. doi: 10.1023/A:1022438616684. doi: 10.1023/A:1022438616684
[53]	W. H. Haemers, C. Parker, V. Pless, V. D. Tonchev, A design and a code invariant under the simple group Co₃, J. Comb. A., 62 (1993), 225-233. doi: 10.1016/0097-3165(93)90045-A. doi: 10.1016/0097-3165(93)90045-A
[54]	V. D. Tonchev, Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs, IEEE T. Inform. Theory, 43 (1997), 1021-1025. doi: 10.1109/18.568714. doi: 10.1109/18.568714
[55]	W. H. Haemers, R. Peeters, J. M. Rijckevorsel, Binary codes of strongly regular graphs, Design. Code. Cryptogr., 17 (1999), 187-209. doi: 10.1023/A:1026479210284. doi: 10.1023/A:1026479210284
[56]	D. Crnković, B. G; Rodrigues, S. Rukavina, L. Simčić, Ternary codes from the strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs, Discrete Math., 312 (2012), 3000-3010. doi: 10.1016/j.disc.2012.06.012. doi: 10.1016/j.disc.2012.06.012
[57]	D. Crnković, M. Maximović, B. Rodrigues, S. Rukavina, Self-orthogonal codes from the strongly regular graphs on up to 40 vertices, Adv. Math. Commun., 10 (2016), 555-582. doi: 10.3934/amc.2016026. doi: 10.3934/amc.2016026
[58]	W. Fish, R. Fray, E. Mwambene, Binary codes from the complements of the triangular graphs, Quaest. Math., 33 (2010), 399-408. doi: 10.2989/16073606.2010.541595. doi: 10.2989/16073606.2010.541595
[59]	M. Grassl, M. Harada, New self-dual additive F4-codes constructed from circulant graphs, Discrete Math., 340 (2017), 399-403. doi: 10.1016/j.disc.2016.08.023. doi: 10.1016/j.disc.2016.08.023
[60]	J. D. Key, B. G. Rodrigues, LCD codes from adjacency matrices of graphs, Appl. Algebr. Eng. Comm., 29 (2018), 227-244. doi: 10.1007/s00200-017-0339-6. doi: 10.1007/s00200-017-0339-6
[61]	D. Leemans, B. G. Rodrigues, Binary codes of some strongly regular subgraphs of the McLaughlin graph, Design. Code. Cryptogr., 67 (2013), 93-109. doi: 10.1007/s10623-011-9589-7. doi: 10.1007/s10623-011-9589-7
[62]	M. Higazy, T. A. Nofal, On network designs with coding error detection and correction application, Comput. Mater. Con., 67 (2021), 3401-3418. doi: 10.32604/cmc.2021.015790. doi: 10.32604/cmc.2021.015790
[63]	W. Fish, J. D. Key, E. Mwambene, Special LCD codes from products of graphs, Appl. Algebr. Eng. Comm., 2021, doi: 10.1007/s00200-021-00517-4. doi: 10.1007/s00200-021-00517-4

Reader Comments

Your name:*

Email:*
© 2022 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)