# Construction of Mutually Orthogonal Graph Squares Using Novel Product Techniques

Authors: A. El-Mesady; Omar Bazighifan
Journal: Journal of Mathematics
 (2022)

---

## Abstract

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.


---

## Body

## 1. Introduction

Graphs are discrete structures consisting of vertices and edges that connect these vertices. Several problems in almost every conceivable discipline can be solved using graph models. Certain problems in physics, chemistry, computer technology, psychology, communication science, linguistics, engineering, sociology, and genetics can be formulated as problems in graph theory. For instance, graphs are used to represent the competition of different species in an environment, to represent who influences whom in an organization, and to represent the outcomes of round-robin tournaments. Also, graphs are used to model relationships between people, collaborations between researchers, telephone calls between telephone numbers, and links between websites, to mention just a few areas. Many branches of mathematics, such as probability, topology, matrix theory, and group theory, have strong connections with graph theory. For standard terminology and notations concerning graph theory, see [1]. Decompositions of complete bipartite graphs have several applications in the design of experiments, graph code generation, and authentication codes [2, 3]. Table 1 shows the nomenclature used in the paper.Table 1
The nomenclature used in the paper.
NomenclaturedxDegree of a vertexxℤnThe group0,1,…,n−1KmComplete graph withm verticesKm,nComplete bipartite graph having two independent sets of sizesm and nCkCycle of lengthkPkPath onk verticesG∪HDisjoint union ofG and HmGm disjoint copies of GMi,jEntry in rowi and column j of a square matrix M⊗Cartesian product operationPnFF−path obtained by replacing each edge in Pn by the graph FIn this paper, we are concerned with an area of combinatorial theory that deals with mutually orthogonalF squares where F is a subgraph of Kn,n. Mutually orthogonal Latin squares (MOLS) are a special case of mutually orthogonal graph squares (MOGS). MOGS are interesting but not attainable for general graphs. Combinatorial design theory 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.Definition 1.
(see [4]). Let F be a subgraph of Kn,n with size n. A square matrix M of order n is an F−square if every element in ℤn=0,1,…,n−1 is found exactly n times in M, and the graphs Fk with EFk=a0,b1:Ma0,b1=k:k∈ℤn are isomorphic to F. The elements of ℤn×0 are used for labeling the rows of M, and the elements of ℤn×1 are used for labeling the columns of M. An edge decomposition of Kn,n by a graph F can be represented by an F−square.Definition 2.
(see [4]). Suppose M1 is an F−square of order n with entries from a set C, and M2 is an F−square of order n with entries from a set D. Then, the two squares M1 and M2 are orthogonal if, for every x∈C and for every y∈D, there exists exactly one cell a0,b1 such that M1a0,b1=x and M2a0,b1=y. A set of λF−squares of order n, say M1,…,Mλ, are called pairwise orthogonal (mutually orthogonal) F−squares (MOGS) if Mp and Mq are orthogonal for all 1≤p<q≤λ. Here, we consider C=D=ℤn=0,1,…,n−1.Theorem 1.
For the bipartite graphF having n edges, Nn,F denotes the maximum number k in a largest possible set of MOGS of Kn,n by F. For every bipartite graph F with n≥2 edges, we have Nn,F≤n.Great efforts have been made to get the solution to several problems concerned with the MOLS since Euler first asked about MOLS to solve the thirty-six officer’s problem. Famous theorems concerning the MOLS were introduced by Bose, Shrikhande, and Parker [5, 6]. Also, Wilson in [7] handled celebrated theorems concerned with the MOLS. Many efforts have been concentrated on refining and finding novel applications for these approaches. The authors of [8] proposed an integrated firefly algorithm based on MOLS, named FA-MOLS, to address the quadratic assignment problem. Liu [9] introduced the packing of Latin squares by BCL algebras. The authors in [10] focused on the existence of orthogonal large sets of partitioned incomplete Latin squares. A large set of disjoint incomplete Latin squares was introduced in [11]. A strategy for producing group-based Sudoku-pair Latin squares was investigated in [12]. The Latin squares were constructed based on the circulant matrix by the authors of [13]. Authentication codes based on orthogonal arrays and Latin squares were proposed in [14]. For a good survey of MOLS, see [15] and the references therein. El-Shanawany [16] proposed the conjecture, Np,Pp+1=p, where Pp+1 is a path with p+1 vertices and p is a prime number. Sampathkumar et al. [17] solved this conjecture. El-Shanawany [18] found Np,Pp+1F. El-Shanawany [19] computed Nn,F=r≥3 where F is disjoint copies of some subgraphs of Kn,n. El-Shanawany and El-Mesady [4] introduced the Kronecker product of MOGS and applied this technique to get a new mutually orthogonal disjoint union of some complete bipartite graph squares. MOGS for disjoint unions of paths were developed in [20]. MOGS for certain graphs were handled by [21]. El-Mesady et al. [22] generalized the MacNeish’s Kronecker product theorem of MOLS. MOGS were used to construct graph-transversal designs and graph-authentication codes in [3, 23]. MOGS are used to construct orthogonal arrays that have many applications [24].The main purpose of this paper is to construct several new results on MOGS. All of the previously mentioned MOGS results motivated us to introduce novel different product techniques to MOGS that yield new MOGS results. The proposed product techniques are the half-starters’ vectors Cartesian product, half-starters’ function product, and graph tensor product. The novelty of the current paper is demonstrated by the fact that it is the first to introduce the MOGS by the aforementioned product techniques. 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. The main difference between this paper and almost all the related study works that we surveyed in this section is that the proposed product techniques are recursive construction techniques that can use all the results in the literature to construct novel results concerned with MOGS. Also, the Kronecker product [4] was applied to the squares, but the half-starters’ vectors Cartesian product is applied to the vectors, the half-starters’ function product is applied to the functions, and the graph tensor product is applied to graphs.The remaining part of the present paper is divided as follows: Section2 is devoted to MOGS from mutually orthogonal half-starters’ vectors. Section 3 constructs MOGS based on the Cartesian product of half-starters’ vectors. MOGS from mutually orthogonal half-starters’ functions are presented in Section 4. Section 5 introduces the tensor products of MOGS. MOGS for complete bipartite graphs by stars based on the tensor product are proved in Section 6. Discussion is presented in Section 7. Section 8 is devoted to the conclusion and future work.


## 2. MOGS from Mutually Orthogonal Half Starters’ Vectors

If we have a graphF which is considered a subgraph of Kn,n with n edges, then the graph F+x is called the x−translate of F and EF+x=a0+x,b1+x:a0,b1∈EF. If the edge a0,b1∈EF, then its length is defined by b−a, where arithmetic operations are calculated modulo n. A graph F is called a half-starter w.r.t. ℤn if EF=n and the edges in F have different lengths that are equivalent to the group ℤn.Theorem 2.
(see [9]). If F is a half-starter, then an edge decomposition of Kn,n can be constructed by finding all the translates of F and taking their union; that is, ∪x∈ℤnEF+x=EKn,n.The vectoruF=u0,u1,…,un−1∈ℤnn=ℤn×⋯×ℤn︷n−times can be used to represent the half-starter F where uk,k∈ℤn, and uk0 is the unique vertex uk,0∈ℤn×0 that belongs to the unique edge of length k in F with EF=uk,uk+k:uk,k∈ℤn. Two half-starters’ vectors uH and uF are said to be orthogonal if ukH−ukF:k∈ℤn=ℤn. A set of half-starters’ vectors uF0,uF1,…,uFλ−1 is mutually orthogonal if uFk and uFl are orthogonal for every 0≤k<l≤λ−1. It is worth noting that each half-starter and its translates of a subgraph F of Kn,n are equivalent to F−square. Hence, the set of k mutually orthogonal half-starters and their translates are equivalent to a set of k mutually orthogonal F−squares.


## 3. MOGS Based on the Cartesian Product of Half-Starters’ Vectors

The Cartesian product of half-starters’ vectors has been defined in literature for constructing orthogonal double covers ofKn,n. This method has been applied to construct orthogonal double covers of Kn,n by new graph classes. The Cartesian product of two vectors corresponding to two half-starter graphs is considered a very special case of the tensor product of these two half-starter graphs.Definition 3.
The tensor product of two graphsG1 and G2,G1×G2 is defined as follows. If a vertex u1 is adjacent to a vertex v1 in G1 and a vertex u2 is adjacent to a vertex v2 in G2, then the vertex u1,u2 is adjacent to the vertex v1,v2 in G1×G2.Example 1.
Figure1 exhibits an example of the graphs G1,G2, and G1×G2.Figure 1
An example for the graphsG1,G2, and G1×G2.Definition 4.
(see [25]). Let G be a graph, and v belongs to the vertex set of G. The number of edges incident at v in G is called the degree (or valency) of the vertex v in G and is denoted by dv. From the degrees of vertices of G, we can construct a sequence which is called a degree sequence of G, when the vertices are taken in the same order. It is customary to put this sequence in nondecreasing or nonincreasing order. This gives a unique sequence.Example 2.
(see [25]). In the graph G of Figure 2, the number within the parentheses indicates the degree of the corresponding vertex. The degree sequence of G is 0,1,2,2,4,4,5.Figure 2
Degrees of vertices for the graphG.Definition 5.
If we have the vectoruG=u0,u1,…,um−1∈ℤmm, then, by determining the repetition number of each element in the vector uG, we get the vector N=n0,n1,…,nm−1, where ni is the repetition number of the element i,i∈ℤm. By the ascending order for the vector N, we get the degree sequence of the vector uG defined by L=l0,l1,…,lm−1, where l0≤l1≤…≤lm−1.Definition 6.
If we have the two vectorsupGp=u0p,u1p,…,um−1p,uqGq=u0q,u1q,…,um−1q and the two vectors u′P=u′0p,u′1P,…,u′m−1P,u′q=u′0q,u′1q,…,u′m−1q, where u′iP=uip+i,u′iq=uiq+i,i∈ℤm, then the two half-starters Gp and Gq are isomorphic if Lp=Lq and LP′=Lq′ or Lp=Lq′ and Lp′=Lq, where Lp is the degree sequence of the vector up,Lp′ is the degree sequence of the vector u′p,Lq is the degree sequence of the vector uq, and Lq′ is the degree sequence of the vector u′q. In our paper, we consider the case of Lp=Lq and LP′=Lq′ for the isomorphism of the two half-starters Gp and Gq.
For Proposition1, if we have the two half-starters G and H which are represented by the vectors vG∈ℤmm and uH∈ℤnn, respectively, then the graph T≅G⊗H is defined by the edge set ET=EG⊗H=viuj,vi+iuj+j:i∈ℤm,j∈ℤn.Proposition 1.
If there arek mutually orthogonal half-starters’ vectors of length m for the graph G, and k mutually orthogonal half-starter’ vectors of length n for the graph H, then there are k mutually orthogonal half-starters’ vectors of length mn for the graph T≅G⊗H.Proof 1.
Forp≠q∈ℤk, let vGs≅G be k mutually orthogonal half-starters’ vectors of length m and vHs≅H be k mutually orthogonal half-starters’ vectors of length n, where vsGs=v0s,v1s,…,vm−1s∈ℤmm and usHs=u0s,u1s,…,un−1s∈ℤnn. Hence,(1)vipGp−viqGq:i∈ℤm=ℤm, (2)uipHp−uiqHq:i∈ℤn=ℤn.
Then,vsGs⊗usHs=v0su0s,v0su1s,v0su2s,…,visujs,…,vm−1sun−1s where i∈ℤm,j∈ℤn. For Tp≅Gp⊗Hp,Tq≅Gq⊗Hq, we conclude from (1) and (2),(3)vipujp−viqujq:ij∈ℤm⊗ℤn=vipGp−viqGqujpHp−ujqHq:i∈ℤm,j∈ℤn=ℤm⊗ℤn.
Hence, from (3), the two half-starters Tp and Tq are orthogonal. Since EGs=vis,vis+i:i∈ℤm and EHs=ujs,ujs+j:j∈ℤn, then(4)EGs⊗Hs=ETs,=visujs,vis+iujs+j:i∈ℤm,j∈ℤn.
Now, we will try to prove the isomorphism of the graphsTs, s∈ℤk. We have ETp=vipujp,vip+iujp+j:i∈ℤm,j∈ℤn=vipujp,v′ipu′jp:i∈ℤm,j∈ℤn and ETq=viqujq,viq+iujq+j:i∈ℤm,j∈ℤn=viqujq,v′iqu′jq:i∈ℤm,j∈ℤn. Since the degree sequence of the vector vp equals the degree sequence of the vector vq, the degree sequence of the vector v′P equals the degree sequence of the vector v′q, the degree sequence of the vector up equals the degree sequence of the vector uq, and the degree sequence of the vector u′p equals the degree sequence of the vector u′q, then the degree sequence of the vector vpup equals the degree sequence of the vector vquq, and the degree sequence of the vector v′pu′p equals the degree sequence of the vector v′qu′q. Hence, the two half-starters Tp and Tq are isomorphic.Example 3.
Letq be a prime >2. Then, we have q mutually orthogonal half-starters’ vectors defined by uisGs=is−i, where i,s∈ℤq and Gs≅Pq+1, see [11]. Hence, we have 3 mutually orthogonal half-starters’ vectors for both P6 and P4, which are vsP6s and usP4s, respectively. Then, we obtain 3 mutually orthogonal half-starters’ vectors wsP6s⊗P4s as shown in Table 2. See Figure 3.
Also, the three MOGS corresponding to the vectorsvsP6s are A0,A1, and A2, the three MOGS corresponding to the vectors usP4s are B0,B1, and B2, and the three MOGS corresponding to the vectors wsP6s⊗P4s are L0,L1, and L2.
Of course inL0,L1, and L2, one can easily replace the ordered pairs 00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32, 40, 41, 42 by 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 to obtain three mutually orthogonal P6⊗P4-squares of order 15, where their elements are the usual symbols.Table 2
The used vectors in Example3.
vsP6s,v′sP6susP4s,u′sP4swsP6s⊗P4s,w′sP6s⊗P4ss=00,4,1,1,4,0,0,3,4,30,2,2,0,0,100,02,02,40,42,42,10,12,12,10,12,12,40,42,42,00,00,01,00,00,01,30,30,31,40,40,41,30,30,31s=10,0,3,4,3,0,1,0,2,20,0,1,0,1,000,00,01,00,00,01,30,30,31,40,40,41,30,30,31,00,01,00,10,11,10,00,01,00,20,21,20,20,21,20s=20,1,0,2,2,0,2,2,0,10,1,0,0,2,200,01,00,10,11,10,00,01,00,20,21,20,20,21,20,00,02,02,20,22,22,20,22,22,00,02,02,10,12,12Figure 3
Three mutually orthogonal half-starters corresponding to the vectorswsP6s⊗P4s.


## 4. MOGS from Mutually Orthogonal Half-Starters’ Functions

In what follows, ifV1=ℤn⊗0 and V2=ℤn⊗1, then the graphs Gfi will be represented by the functions fi:V1⟶V2. The edge set of the graphs Gfi is EGfi=x,fix:x∈V1. Every graph from the graphs Gfi represents unions of stars which have the same direction where every vertex x belongs to V1 has a degree of one, that is, dx=1. The graph Gf is called f− half-starter if EGf=∪x∈V1x,fx, where Gf is a subgraph of Kn,n with n edges and f:V1⟶V2.Definition 7.
(see [9]). Let z∈ℤn. Then, the graph Gf+z=x,fx+z:x,fx∈EGf is called the z,f−translate of Gf.Remark 1.
(see [9]). The union of all translates of Gf forms an edge decomposition of Kn,n, that is, ∪z∈ℤnEGf+z=EKn,n.
Definition7 and Remark 1 show that every f− half-starter graph Gf and the translates are equivalent to Gf-square.
LetGfi≅G,i∈ℤk be subgraphs of Kn,n with EG=n. Then, the set Gfi is called a set of k mutually orthogonal subgraphs, if fix−fjx:x∈ℤn=ℤn for all i,j∈ℤk and i≠j. If the two half-starters Gf and Gg are orthogonal, then the two sets of translates of Gf and Gg are orthogonal. A set of edge decompositions Hfi=∪z∈ℤnEGfi+z is a set of k MOGS if Hfi and Hfj are orthogonal for all i,j∈ℤk and i≠j.Example 4.
Letfix=x2+ix be f− half-starter graphs Gfi≅K2∪K1,2 of K3,3 for all i,x∈ℤ3. The edge set of the graphs Gfi and their translates are shown in Tables 3, 4, and 5.
Hence, we deduce the following three mutually orthogonalK2∪K1,2-squares:(5)L0=012201201,L1=012120012,L2=012012120.Table 3
The graphGf0 and it’s translates for Example 4.
EGf0=x,f0xEGf0+1EGf0+20,00,10,21,11,21,02,12,22,0Table 4
The graphGf1 and it’s translates for Example 4.
EGf1=x,f1xEGf1+1EGf1+20,00,10,21,21,01,12,02,12,2Table 5
The graphGf2 and it’s translates for Example 4.
EGf2=x,f2xEGf2+1EGf2+20,00,10,21,01,11,22,22,02,1Definition 8.
For thef− half-starter graph Gf represented by the function f:V1⟶V2, where V1=ℤn⊗0,V2=ℤn⊗1, and EGf=x,fx:x∈V1, we have dx=1 for all x∈V1. By determining the degree of each vertex belonging to V2, from Gf, we get the vector N=d01,d11,…,dn−11, where di1 is the degree of the vertex i1,i1∈ℤn⊗1. By the ascending order for the vector N, we get the degree vector of Gf denoted by Lf=l0,l1,…,ln−1 where l0≤l1≤…≤ln−1.Definition 9.
If we have thef-half-starter graph Gf represented by the function f:V1⟶V2 and the g-half-starter graph Gg represented by the function g:V1⟶V2, then Gf and Gg are isomorphic if Lf=Lg, where Lf is the degree vector of Gf and Lg is the degree vector of Gg.
We shall denote byNn,Gfi the maximal number of fi−half-starter graphs Gfi in the largest possible set of mutually orthogonal subgraphs Gfi in Kn,n,i∈ℤk. Hereafter, if we have Nm,Gfi≥λ, where i∈ℤλ and Gfi≅G having m edges and Nn,Ggi≥μ, where i∈ℤμ and Ggi≅H having n edges and minλ,μ=k, then we obtain Nmn,Ghi≥k, where i∈ℤk and Ghi≅Gfi⊗Ggi by Proposition 2. Also, we present some results as direct applications to Proposition 2. In the following, if there is no danger of ambiguity, if x,y∈ℤm⊗ℤn, we can write x,y as xy.Proposition 2.
IfNm,Gfi≥λ, where i∈ℤλ and Gfi≅G have m edges, Nn,Ggi≥μ, where i∈ℤμ and Ggi≅H have n edges, and minλ,μ=k, then Nmn,Ghi≥k, where Ghi≅Gfi⊗Ggi are isomorphic graphs having mn edges.Proof 2.
Letfi−half-starter graphs Gfi be represented by the functionsfix,i∈ℤk,x∈ℤm and gi−half-starter graphs Ggi be represented by the functions giy,i∈ℤk,y∈ℤn. Then, we obtain the hi−half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions(6)hixy=fixgiy.
Sincehpxy−hqxy=fpxgpy−fqxgqy=fpx−fqxgpy−gqy:p,q∈ℤk,p≠q=ℤm⊗ℤn, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,fix and EGgi=y,giy, then EGhi=xy,fixgiy. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤk,p≠q, we have Lfp=Lfq and Lgp=Lgq, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq. Hence, Ghp and Ghq are isomorphic.
All the following results are based on (i) Proposition2 and (ii) the following ingredients (see [9]).(i)
Letn>2 be a prime number. Then, Nn,K1,1∪n−1/2K1,2=n, and the fi−half-starter graphs Gfi≅K1,1∪n−1/2K1,2 are represented by the functions fix=x2+ix, where i,x∈ℤn.(ii)
Letn be a prime number. Then, Nn,nK1,1=n−1 and the fi− half-starter graphs Gfi≅nK1,1 are represented by the functions fix=ix, where x∈ℤn,i∈ℤn/0.(iii)
Letn>2 be a prime number. Then, Nn,n−2K1,1∪K1,2≥n−1, and the fi− half-starter graphs Gfi≅n−2K1,1∪K1,2 are represented by the functions fix=0;x=01+ix;i,x∈ℤn.(iv)
Letn=9. Then, N9,K1,3∪3K1,2≥3, and the fi− half-starter graphs Gfi≅K1,3∪3K1,2 are represented by the functions fix=x2+ix, where x∈ℤ9,i∈ℤ3.(v)
Letn=7. Then N7,3K1,1∪2K1,2≥4, for i∈ℤ4, the fi− half-starter graphs Gfi≅3K1,1∪2K1,2 are represented by the functions(7)fix=0;x=0,1+4i;x=4,2+i;x=1,4+ix;x=2,5,6+ix;x=3,6.
These knownfi− half-starter graphs Gfi are the ingredients for the following results. These ingredients are some of the literature results and are not all of the literature results.Theorem 3.
Letn,m be odd primes. Then, Nmn,G1≥k, where k=minm,n−1 and G1≅nK1,1∪m−1n/2K1,2.Proof 3.
We havek mutually orthogonal fi− half-starter graphs Gfi≅K1,1∪m−1/2K1,2, which are represented by the functions fix=x2+ix, where x∈ℤm,i∈ℤk (ingredient (i)) and k mutually orthogonal gi− half-starter graphs Ggi≅nK1,1, which are represented by the functions giy=i+1y, where y∈ℤn,i∈ℤk (ingredient (ii)). Then, we obtain k mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=x2+ixi+1y. Since hpxy−hpxy=x2+pxp+1y−x2+qxq+1y=x2+px−x2+qxp+1y−q+1y:p,q∈ℤk,p≠q=ℤm⊗ℤn, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,x2+ix and EGgi=y,i+1y, then EGhi=xy,x2+ixi+1y. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤk,p≠q, we have Lfp=Lfq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2 and Lgp=Lgq=1,1,…,1︷n, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2⊗1,1,…,1︷n. Hence, Ghp and Ghq are isomorphic.Theorem 4.
Letn,m be primes. Then, Nmn,G2≥k, where k=minm,n−1 and G2≅n−2K1,1∪m−1n−2+2/2K1,2∪m−1/2K1,4.Proof 4.
We havek mutually orthogonal fi− half-starter graphs Gfi≅K1,1∪m−1/2K1,2, which are represented by the functions fix=x2+ix, where x∈ℤm,i∈ℤk (ingredient (i)) and k mutually orthogonal gi− half-starter graphs Ggi≅n−2K1,1∪K1,2, which are represented by the functions giy=0;y=01+i+1y;y∈ℤn/0,i∈ℤk (ingredient (iii)). Then, we obtain k mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=x2+ixgiy. Since hpxy−hpxy=x2+pxgpy−x2+qxgqy=x2+px−x2+qxgpy−gqy:p,q∈ℤk,p≠q=ℤm⊗ℤn, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,x2+ix and EGgi=y,giy, then EGhi=xy,x2+ixgiy. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤk,p≠q, we have Lfp=Lfq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2 and Lgp=Lgq=0,1,1,…,1︷n−2,2, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lfp=Lfq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2⊗0,1,1,…,1︷n−2,2. Hence, Ghp and Ghq are isomorphic.Theorem 5.
Letm be odd prime. Then, N9m,G3≥3, where G3≅K1,3∪3K1,2∪m−1/2K1,6∪3m−1/2K1,4.Proof 5.
We havem mutually orthogonal fi− half-starter graphs Gfi≅K1,1∪m−1/2K1,2, which are represented by the functions fix=x2+ix, where x∈ℤm,i∈ℤk (ingredient (i)) and 3 mutually orthogonal gi− half-starter graphs Ggi≅K1,3∪3K1,2, which are represented by the functions giy=y2+iy,y∈ℤ9,i∈ℤ3 (ingredient (iv)). Since minm,3=3, then we obtain 3 mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=x2+ixy2+iy,i∈ℤ3. Since hpxy−hpxy=x2+pxy2+py−x2+qxy2+qy=x2+px−x2+qxy2+py−y2+qy:p,q∈ℤ3,p≠q=ℤm⊗ℤ9, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,x2+ix and EGgi=y,y2+iy, then EGhi=xy,x2+ixy2+iy. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤ3,p≠q, we have Lfp=Lfq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2 and Lgp=Lgq=0,0,0,0,0,2,2,2,3, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2⊗0,0,0,0,0,2,2,2,3 Hence, Ghp and Ghq are isomorphic.Theorem 6.
Letm>3 be prime. Then, N7m,G4≥4, where G4≅3K1,1∪3m−1+4/2K1,2∪m−1K1,4.Proof 6.
We havem mutually orthogonal fi− half-starter graphs Gfi≅K1,1∪m−1/2K1,2, which are represented by the functions fix=x2+ix, where x∈ℤm,i∈ℤk (ingredient (i)) and 4 mutually orthogonal gi− half-starter graphs Ggi≅3K1,1∪2K1,2, which are represented by the functions(8)giy=0;y=0,1+4i;y=4,2+i;y=1,4+iy;y=2,5,6+iy;y=3,6,where i∈ℤ4 (ingredient (v)). Since minm,4=4, then we obtain 4 mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=x2+ixgiy. Since hpxy−hpxy=x2+pxgpy−x2+qxgqy=x2+px−x2+qxgpy−gqy:p,q∈ℤ4,p≠q=ℤm⊗ℤ7, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,x2+ix and EGgi=y,giy, then EGhi=xy,x2+ixgiy. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤ4,p≠q, we have Lfp=Lfq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2 and Lgp=Lgq=0,0,1,1,1,2,2, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq=0,0,…,0︷m−1/2,1,2,2,…,2︷m−1/2⊗0,0,1,1,1,2,2. Hence, Ghp and Ghq are isomorphic.Theorem 7.
Letn,m be primes. Then Nmn,G5≥k, where k=minm−1,n−1 and G5≅mn−2K1,1∪m1,2.Proof 7.
We havem−1 mutually orthogonal fi− half-starter graphs Gfi≅mK1,1, which are represented by the functions fix=i+1x, where x∈ℤm,i∈ℤk (ingredient (ii)) and n−1 mutually orthogonal gi− half-starter graphs Ggi≅n−2K1,1∪K1,2, which are represented by the functions giy=0;y=01+i+1y;y∈ℤn/0,i∈ℤk (ingredient (iii)). Then, we obtain k mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=i+1xgiy. Since hpxy−hpxy=p+1xgpy−q+1xgqy=p+1x−q+1xgpy−gqy:p,q∈ℤk,p≠q=ℤm⊗ℤn, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,i+1x and EGgi=y,giy, then EGhi=xy,i+1xgiy. Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤk,p≠q, we have Lfp=Lfq=1,1,…,1︷m and Lgp=Lgq=0,1,1,…,1︷n−2,2, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq=1,1,…,1︷m⊗0,1,1,…,1︷n−2,2. Hence, Ghp and Ghq are isomorphic.Theorem 8.
Letm>3 be prime. Then N9m,G6≥3, where G6≅m−2K1,3∪3m−2K1,2∪K1,6∪3K1,4.Proof 8.
We have3 mutually orthogonal fi− half-starter graphs Gfi≅m−2K1,1∪K1,2, which are represented by the functions fix=0;x=01+i+1x;x∈ℤm/0,i∈ℤ3 (ingredient (iii)) and 3 mutually orthogonal gi− half-starter graphs Ggi≅K1,3∪3K1,2, which are represented by the functions giy=y2+iy,y∈ℤ9,i∈ℤ3 (ingredient (iv)). Then, we obtain 3 mutually orthogonal hi− half-starter graphs Ghi≅Gfi⊗Ggi, which are represented by the functions hixy=fixy2+iy. Since hpxy−hpxy=fpxy2+py−fqxy2+qy=fpx−fqxy2+py−y2+qy:p,q∈ℤ3,p≠q=ℤm⊗ℤ9, then Ghp and Ghq are orthogonal. The edge set of the graphs Ghi can be obtained as follows, since EGfi=x,fix and EGgi=y,y2+iy, then EGhi=xy,fixy2+iy Now, we want to prove the isomorphism of the two graphs Ghp and Ghq. For p,q∈ℤ3,p≠q, we have Lfp=Lfq=0,1,1,…,1︷m−2,2 and Lgp=Lgq=0,0,0,0,0,2,2,2,3, then for Ghp≅Gfp⊗Ggp and Ghq≅Gfq⊗Ggq, the degree vector of Ghp is equal to the degree vector of Ghq. This means that Lhp=Lhq=0,1,1,…,1︷m−2,2⊗0,0,0,0,0,2,2,2,3 Hence, Ghp and Ghq are isomorphic.Example 5.
Letfix=x2+ix be fi− half-starter graphs Gfi of K3,3 for all i,x∈ℤ3 and giy=y2+iy be gi− half-starter graphs Ggi of K5,5 for all i,x∈ℤ5. Since min3,5=3, then we obtain 3 hi− half-starter graphs Ghi of K15,15, which are represented by the functions hixy=fixgiy for all i∈ℤ3. The edge sets of Gfi,Ggi, and Ghi are shown in Tables 6, 7, and 8, where Gfi≅K2∪K1,2,Ggi≅K2∪2K1,2, and Ghi≅K2∪3K1,2∪2K1,4. Also, the three MOGS corresponding to the functions fix are A0,A1, and A2, the three MOGS corresponding to the functions giy are B0,B1, and B2, and the three MOGS corresponding to the functions hixy are C0,C1, and C2. See Figures 4, 5, and 6.(9)A0=012201201,A1=012120012,A2=012012120,B0=0123440123123401234040123,B1=0123434012401233401201234,B2=0123423401234010123412340,C0=000102030410111213142021222324040001020314101112132420212223010203040011121314102122232420010203040011121314102122232420040001020314101114132420212223202122232400010203041011121314242021222304000102031410111213212223242001020304001112131410212223242001020304001112131410242021222304000102031410111213202122232400010203041011121314242021222304000102031410111213212223242001020304001112131410212223242001020304001112131410242021222304000102031410111213,C1=000102030410111213142021222324030400010213141011122324202122040001020314101112132420212223030400010213141011122324202122000102030410111213142021222324101112131420212223240001020304131410111223242021220304000102141011121324202122230400010203131410111223242021220304000102101112131420212223240001020304000102030410111213142021222324030400010213141011122324202122040001020314101112132420212223030400010213141011122324202122000102030410111213142021222324,C2=000102030410111213142021222324020304000112131410112223242021020304000112131410112223242021000102030410111213142021222324010203040011121314102122232420000202030410111213142021222324020304000112131410112223242021020304000112131410112223242021000102030410111213142021222324010203040011121314102122232420101112131420212223240001020304121314101122232420210203040001121314101122232420210203040001101112131420212223240001020304111213141021222324200102030400.
In the following section, we present the general tensor product technique for constructing the MOGS. As stated above, the MOGS represent mutually orthogonal covers (MOCs) of complete bipartite graphs. Ak mutually orthogonal covers (k MOCs) of the complete bipartite graph Kn,n by F is a family G of isomorphic copies of a given subgraph F such that they cover every edge of Kn,nk times and the intersection of any two of them contains at most one edge.Table 6
The edge set of the graphsGf0, Gf1, and Gf2 for Example 5.
EGf0=x,f0xEGf1=x,f1xEGf2=x,f2x0,00,00,01,11,21,02,12,02,2Table 7
The edge set of the graphsGg0, Gg1, and Gg2 for Example 5.
EGg0=y,g0yEGg1=y,g1yEGg2=y,g2y0,00,00,01,11,21,32,42,12,33,43,23,04,14,04,4Table 8
The edge set of the graphsGh0, Gh1, and Gh2 for Example 5.
EGh0EGh1EGh200,0000,0000,0001,0101,0201,0302,0402,0102,0303,0403,0203,0004,0104,0004,0410,1010,2010,0011,1111,2211,0312,1412,2112,0313,1413,2213,0014,1114,2014,0420,2020,2020,2021,2121,0221,2322,2422,0122,2323,2423,0223,2024,2124,0024,24Figure 4
Gh0≅K2∪3K1,2∪2K1,4 corresponding to the 00 values in C0.Figure 5
Gh1≅K2∪3K1,2∪2K1,4 corresponding to the 00 values in C1.Figure 6
Gh2≅K2∪3K1,2∪2K1,4 corresponding to the 00 values in C2.


## 5. Tensor Products of MOCs

LetA and B be simple graphs, then the tensor product, A×B, of A and B, is the graph with the vertex set VA×VB and the edge set EA×B=a,bc,d:ac∈EA and bd∈EB. If the simple graphs A and B are bipartite with bipartitions E,F and Y,Z, respectively, then the induced subgraphs A×BE×Y∪F×Z and A×BE×Z∪F×Y are called the weak-tensor products of A and B. We denote the weak-tensor product A×BE×Y∪F×Z by A⊛B.Proposition 3.
If there arek MOCs of Km,m by A and k MOCs of Kn,n by B, then there are k MOCs of Kmn,mn by A⊛B.Proof 9.
Let∩i=1kAi, where Ai=A1i,A2i,...,Ami be k MOCs of Km,m by A on VKm,m=E,F where E=e1,...,em and F=f1,...,fm is the bipartition of Km,m, and let ∩i=1kBi, where Bi=B1i,B2i,...,Bni be k MOCs of Kn,n by B on VKn,n=Y,Z where Y=y1,...,yn and Z=z1,...,zn is the bipartition of Kn,n. Let W=VKmn,mn and the partite sets of Kmn,mn be ep,yq:1≤p≤m,1≤q≤n and fp,zq:1≤p≤m,1≤q≤n. Consider the set Ci=Api×BqiW:1≤p≤m,1≤q≤n,1≤i≤k, of subgraphs of Kmn,mn. Clearly, Api×BqiW≅A⊛B,1≤p≤m,1≤q≤n,1≤i≤k,sinceApi≅AandBqi≅B.Claim 1.
Every edge ofKmn,mn occurs in exactly k graphs of ∪i=1kCi.
Consider an arbitrary edgees,ytfu,zv of Kmn,mn. Since ∪i=1kAi and ∪i=1kBi are k MOCs of Km,m by A and k MOCs of Kn,n by B, respectively, the edges esfu and ytzv are, respectively, in exactly k graphs of ∪i=1kAi and ∪i=1kBi. Let the k graphs containing esfu be At11,At22,…,Atkk and that of ytzv be Br11,Br22,…,Brkk. Then, the k graphs containing the edge es,ytfu,zv are At11×Br11W,At22×Br22W,…,Atkk×BrkkW.Claim 2.
Leti∈1,2,…,k. Any two graphs in Ci have no edges in common.
The two graphsAt1i×Br1iW and At2i×Br2iW have no edges in common, because EAt1i∩EAt2i=∅ and EBr1i∩EBr2i=∅.Claim 3.
Any graph inCx and any graph in Cy have exactly one edge in common, 1≤x<y≤k.
The two graphsAt1x×Br1xW and At2y×Br2yW have exactly one edge in common, since EAt1x∩EAt2y=1 and EBr1x∩EBr2y=1.
By Claims1,2, and 3,∪i=1kCi is k MOCs of Kmn,mn by A⊛B.


## 6. MOCs of Complete Bipartite Graphs Based on Tensor Product

All the following results are based oni the tensor product in Proposition 3 and ii the existence of MOCs for some classes of graphs. These graphs can be used as ingredients for the tensor product to obtain new MOCs. See [9] for the ingredients from i to iv. Addition and subtraction are calculated modulo n for the following ingredients.(i)
Let∪i=1nAi where Ai=A1i,A2i,…,Ani be n MOCs of Kn,n byK1,1∪n−1/2K1,2,EAj+1i=β,j+i−1β+β2,j,β∈Zn,n. be a prime >2.(ii)
Let∪i=1n−1Ai, where Ai=A1i,A2i,...,Ani be n−1 MOCs of Kn,n by n−2K1,1∪K1,2,EAj+1i=0,0,β,iβ+j+1,j∈Zn,β∈1,2,…,n−1,n be a prime >2.(iii)
Ifn=9, then the 3 MOCs of K9,9 by K1,3∪3K1,2are∪i=13Ai, where Ai=A1i,A2i,...,A9i,EAj+1i=α,α2+i−1α+j,j,α∈Z9.(iv)
Ifn=7, then the4 MOCs of K7,7 by3K1,1∪2K1,2are∪i=14Ai, where Ai=A1i,A2i,...,A7i, for j∈Z7,(10)EAj+11=0,0+j,1,2+j,2,4+j,3,6+j,4,1+j,5,4+j,6,6+j,EAj+12=0,0+j,1,3+j,2,6+j,3,2+j,4,5+j,5,2+j,6,5+j,EAj+13=0,0+j,1,4+j,2,1+j,3,5+j,4,2+j,5,0+j,6,4+j,EAj+14=0,0+j,1,5+j,2,3+j,3,1+j,4,6+j,5,5+j,6,3+j.(v)
Ifn=4, then the3 MOCs of K4,4 by 2K1,2are∪i=13Ai (follows from Theorem 1 in [4], by setting α=0,β=1,γ=2, and δ=3, where Ai=A1i,A2i,A3i,A4i,(11)EA11=0,0,1,2,2,0,3,2,EA21=0,3,1,1,2,3,3,1,EA31=0,2,1,0,2,2,3,0,EA41=0,1,1,3,2,1,3,3,EA32=0,0,1,1,2,1,3,0,EA42=0,1,1,0,2,0,3,1,EA13=0,1,1,1,2,2,3,2,EA23=0,3,1,3,2,1,3,1,EA33=0,3,1,3,2,0,3,0,EA43=0,0,1,0,2,3,3,3.These known MOCs are the ingredients for the tensor product to obtain the following results. Note that we used some of the ingredients from the literature.Theorem 9.
Letm,n be odd primes and k=minn,m−1. Then, there are k MOCs of Kmn,nm by m−2K1,1∪n−1m+2+2/2K1,2∪n−1/2K1,4.Proof 10.
We haven MOCs of Kn,n by K1,1∪n−1/2K1,2 (ingredient (i)) and m−1 MOCs of Km,m by m−2K1,1∪K1,2 (ingredient (ii)). If minn,m−1=k, then we construct k MOCs of Kmn,nm by m−2K1,1∪n−1m+2+2/2K1,2∪n−1/2K1,4 (Proposition 3).Theorem 10.
Letn be odd prime. Then, there are 3 MOCs of K9n,9n by K1,3∪3K1,2∪n−1/2K1,6∪3n−1/2K1,4.Proof 11.
We haven MOCs of Kn,n by K1,1∪n−1/2K1,2 (ingredient (i)) and 3 MOCs of K9,9 by K1,3∪3K1,2 (ingredient (iii)). Then, we construct 3 MOCs of K9n,9n by K1,3∪3K1,2∪n−1/2K1,6∪3n−1/2K1,4 (Proposition 3).Theorem 11.
Letn be odd prime. Then, there are 3 MOCs of K4n,4n by 2K1,2∪n−1K1,4.Proof 12.
We haven MOCs of Kn,n by K1,1∪n−1/2K1,2 (ingredient (i)) and 3 MOCs of K4,4 by 2K1,2 (ingredient (v)). Then, we construct 3 MOCs of K4n,4n by 2K1,2∪n−1K1,4 (Proposition 3).Theorem 12.
Letn be odd prime. Then, there are 3 MOCs of K9n,9n by n−2K1,3∪3n−2K1,2∪K1,6∪3K1,4.Proof 13.
We haven−1 MOCs of Kn,n by n−2K1,1∪K1,2 (ingredient (ii)) and 3 MOCs of K9,9 by K1,3∪3K1,2 (ingredient (iii)). Then, we construct 3 MOCs of K9n,9n by n−2K1,3∪3n−2K1,2∪K1,6∪3K1,4 (Proposition 3).Theorem 13.
Letn be odd prime. Then, there are 4 MOCs of K7n,7n by 3K1,1∪3n−1/2K1,2∪n−1K1,4.Proof 14.
We haven MOCs of Kn,nbyK1,1∪n−1/2K1,2 (ingredient (i)) and 4 MOCs of K7,7by (3K1,1∪2K1,2 (ingredient (iv)). Then, we construct 4 MOCs of K7n,7n by 3K1,1∪3n+1/2K1,2∪n−1K1,4 (Proposition 3).Example 6.
We have3 mutually orthogonal covers of K3,3 by P3∪K2, shown in Figure 7, and 3 mutually orthogonal covers of K3,3 by P4, shown in Figure 8. Hence, we construct 3 mutually orthogonal covers of K9,9 by P3∪K2⊛P4, shown in Figure 9.Figure 7
3 mutually orthogonal covers of K3,3 by P3∪K2.Figure 8
3 mutually orthogonal covers of K3,3 by P4.Figure 9
3 mutually orthogonal covers ofK9,9 by P3∪K2⊛P4.


## 7. Discussion

All the results in this paper are based on recursive construction techniques as stated above. In the literature, the Kronecker product of graph squares has been used to construct some results for MOGS. Herein, we defined three novel product techniques, which are the Cartesian product of half-starters’ vectors, the half-starters’ function product, and the graph tensor product. Some graphs can be represented by vectors, so the Cartesian product can be used with this class of graphs. Other graphs cannot be represented by vectors but can be represented by functions; hence, the function product can be used with this class of graphs. In addition, there is a third class of graphs that cannot be represented by vectors and functions; in this case, the tensor product of graphs is applied to construct the MOGS. All the results from the literature of MOGS with small orders can be used to get MOGS with higher orders by applying the new product techniques defined in this paper. The main results are Propositions1, 2, and 3, which introduce the construction techniques based on the defined novel product techniques. All the remaining results in the paper are direct applications to these propositions. These results are MOGS for disjoint unions of stars such as nK1,1∪m−1n/2K1,2,n−2K1,1∪m−1n−2+2/2K1,2∪m−1/2K1,4,K1,3∪3K1,2∪m−1/2K1,6∪3m−1/2K1,4,mn−2K1,1∪mK1,2, and 3K1,1∪3n+1/2K1,2∪n−1K1,4. All the constructed results in this paper can be used to generate new graph-orthogonal arrays, new graph-authentication codes, and new graph-transversal designs [3, 23]. They can also be used in the design of experiments [24].


## 8. Conclusion

In conclusion, we can say that the proposed novel product techniques are helping tools for constructing several new results concerned with the MOGS that have not been constructed before. It is clear that the proposed product techniques cannot be used to construct MOGS with prime order. In future work, we will try to find new recursive construction techniques for the MOGS.



---

*Source: 9722983-2022-10-10.xml*