Complete Multipartite Graphs Decompositions Using Mutually Orthogonal Graph Squares

被引:0
作者
El-Mesady A. [1 ]
Al-Mdallal Q. [2 ]
Abdeljawad T. [3 ]
机构
[1] Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf
[2] Department of Mathematical Sciences, UAE University, P.O. Box 15551, Al-Ain
[3] Department of Mathematics and Sciences, Prince Sultan University, P. O. Box 66833, Riyadh
关键词
Covering; Decomposition; Multipartite graph;
D O I
10.1007/s40819-023-01534-2
中图分类号
学科分类号
摘要
Graph theory is a part of mathematics known as combinatorics, and it is one of the most active branches of modern algebra, having numerous applications in several fields such as network engineering, computer science engineering, and electrical engineering. A partition of the edge set of a graph G that induces a copy of a graph H is called an H-decomposition of a graph G. If G has an H-decomposition, it is said to be decomposed by H. Claw decomposition, clique decomposition, cycle decomposition, path decomposition, bipartite decomposition, and so on are examples of decomposition problems. Some of them are utilized in filing theory for combinatorial file organization schemes, and others are used in statistics for construction schemes of experimental designs. Herein, we are concerned with decompositions of complete multipartite graphs using mutually orthogonal graph squares for complete bipartite graph. For mutually orthogonal Latin squares, mutually orthogonal graph squares are seen as a generalization. The novelty of this study is demonstrated by the fact that it is the first to present complete multipartite graph decompositions by mutually orthogonal graph squares. In the literature, there are several results for mutually orthogonal graph squares. This help in decomposing the complete multipartite graphs using several graph classes. In the end, we introduce some possible applications of our results in constructing graph-orthogonal arrays, graph-transversal designs, and authentication codes. © 2023, The Author(s), under exclusive licence to Springer Nature India Private Limited.
引用
收藏
相关论文
共 26 条
[1]  
Tazawa S., Ushio K., Yamamoto S., Partite-claw-decomposition of a complete multi-partitegraph, Hiroshima Math. J., 8, pp. 195-206, (1978)
[2]  
Tazawa S., Claw-decomposition and evenly-partite-claw-decomposition of complete multi-partite graphs, Hiroshima Math. J., 9, pp. 503-531, (1979)
[3]  
Ushio K., Tazawa S., Yamamoto S., On claw-decomposition of a complete multipartite graph, Hiroshima Math. J., 8, pp. 207-210, (1978)
[4]  
Ushio K., On Balanced Claw Designs of Complete Multi-Partite Graphs, (1979)
[5]  
Ushio K., On balanced claw-decomposition of a complete multi-partite graph, Memoirs Niihama Tech College, 16, pp. 29-33, (1980)
[6]  
Yamamoto S., Ikeda H., Shige-eda S., Ushio K., Hamada N., On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J., 5, pp. 33-42, (1975)
[7]  
Balogh J., Kostochka A., Lavrov M., Liu X., Monochromatic connected matchings in 2-edge‐colored multipartite graphs, J. Gr. Theory, (2022)
[8]  
Figueroa A.P., Llano B., Olsen M., Rivera-Campo E., On the acyclic disconnection of multipartite tournaments, Discrete Appl. Math., 160, 10-11, pp. 1524-1531, (2012)
[9]  
Figueroa A.P., Montellano-Ballesteros J.J., Olsen M., Strong subtournaments and cycles of multipartite tournaments, Discrete Math., 339, 11, pp. 2793-2803, (2016)
[10]  
Galeana-Sanchez H., Hernandez-Cruz C., Arumugam S., k-kernels in multipartite tournaments, AKCE Int. J. Gr. Comb., 8, 2, pp. 181-198, (2011)