Complete Multipartite Graphs Decompositions Using Mutually Orthogonal Graph Squares

A. El-Mesady, Qasem Al-Mdallal, Thabet Abdeljawad

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number65
JournalInternational Journal of Applied and Computational Mathematics
Issue number5
Publication statusPublished - Oct 2023


  • Covering
  • Decomposition
  • Multipartite graph

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Complete Multipartite Graphs Decompositions Using Mutually Orthogonal Graph Squares'. Together they form a unique fingerprint.

Cite this