Construction of Mutually Orthogonal Graph Squares Using Novel Product Techniques

Sets of mutually orthogonal Latin squares prescribe the order in which to apply different treatments in designing an experiment to permit effective statistical analysis of results, they encode the incidence structure of finite geometries, they encapsulate the structure of finite groups and more general algebraic objects known as quasigroups, and they produce optimal density error-correcting codes. This paper gives some new results on mutually orthogonal graph squares. Mutually orthogonal graph squares generalize orthogonal Latin squares interestingly. Mutually orthogonal graph squares are an area of combinatorial design theory that has many applications in optical communications, wireless communications, cryptography, storage system design, algorithm design and analysis, and communication protocols, to mention just a few areas. In this paper, novel product techniques of mutually orthogonal graph squares are considered. Proposed product techniques are the half-starters’ vectors Cartesian product, half-starters’ function product, and tensor product of graphs. It is shown that by taking mutually orthogonal subgraphs of complete bipartite graphs, one can obtain enough mutually orthogonal subgraphs in some larger complete bipartite graphs. Also, we try to find the minimum number of mutually orthogonal subgraphs for certain graphs based on the proposed product techniques. As a direct application to the proposed different product techniques, mutually orthogonal graph squares for disjoint unions of stars are constructed. All the constructed results in this paper can be used to generate new graph-orthogonal arrays and new authentication codes.