TY - JOUR

T1 - Complete Multipartite Graphs Decompositions Using Mutually Orthogonal Graph Squares

AU - El-Mesady, A.

AU - Al-Mdallal, Qasem

AU - Abdeljawad, Thabet

N1 - Funding Information:
The author Thabet Abdeljawad would like to thank Prince Sultan University for the support through TAS research lab.
Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Nature India Private Limited.

PY - 2023/10

Y1 - 2023/10

N2 - 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.

AB - 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.

KW - Covering

KW - Decomposition

KW - Multipartite graph

UR - http://www.scopus.com/inward/record.url?scp=85169084264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85169084264&partnerID=8YFLogxK

U2 - 10.1007/s40819-023-01534-2

DO - 10.1007/s40819-023-01534-2

M3 - Article

AN - SCOPUS:85169084264

SN - 2349-5103

VL - 9

JO - International Journal of Applied and Computational Mathematics

JF - International Journal of Applied and Computational Mathematics

IS - 5

M1 - 65

ER -