# On Graph-Transversal Designs and Graph-Authentication Codes Based on Mutually Orthogonal Graph Squares

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

---

## Abstract

Combinatorial designs have many interesting and genuine wide applications in areas including analysis and design of algorithms, cryptography, analysis and design of experiments, storage system design, tournament scheduling, optical communications, and computer networks to mention just a few areas. In this paper, we are concerned with the transversal designs and authentication codes as direct applications of combinatorial designs. The novelty of the current paper is demonstrated by the fact that it is the first to introduce the transversal designs and authentication codes by the mutually orthogonal graph squares (MOGS); we call them graph-transversal designs and graph-authentication codes, respectively. Here, the major contributions are the constructions of graph-transversal designs and graph-authentication codes based on several classes of graphs. Also, we present several results such as path-transversal designs, cycle-transversal designs, and disjoint unions of stars-transversal designs.


---

## Body

## 1. Introduction

The development of combinatorial design theory is considered one of the remarkable successes, deep connections with mathematics, unanticipated applications, and the desire to provide ordered objects from apparent chaos. The celebrated successes of combinatorial design theory have appeared in the eighteenth and nineteenth centuries by the research of Euler, Cayley, Kirkman, Hamilton, Moore, Sylvester, and others. In the 1920s, combinatorial design theory became a ﬁeld intimately connected to the applications after Fisher and his school evolved the mathematics of experimental designs. Bose and his colleagues discovered deep interactions between the mathematical nascent field and the number theory, ﬁnite geometry, error-correcting codes, group theory, and finite fields in the 1930s for a good survey on the combinatorial designs and their applications, see [1, 2].A decompositionH=H1,…,Hl of a graph F is a partition of its edge set EF into edge-disjoint isomorphic subgraphs H1,…,Hl. If all these subgraphs are isomorphic to G, then H is a decomposition of F by G. A decomposition of the complete bipartite graph Km,m by mK2 and a Latin square of the order m are equivalent, where the Latin square can be defined as follows.Table 1
The 12 Latin squares of Example1.
M1=123312231M2=123231312M3=132321213M4=132213321M5=213321132M6=213132321M7=231312123M8=231123312M9=312231123M10=312123231M11=321213132M12=321132213Definition 1.
(see [2]). Suppose A is an m-set. Then, a Latin square of order m is an m×m array M with entries from A, such that all the rows and the columns of M are considered permutations of A.Example 1.
(see [2]). Suppose A=1,2,3. Then, there are precisely 12 Latin squares defined on A as shown in Table 1.Definition 2.
(see [2]). Let M1 be a Latin square with order m and entries belong to the set A and M2 be a Latin square with order m and entries belong to the set B. Then, M1 and M2 are orthogonal if, for every x∈A and for every y∈B, there is precisely one cell a,b where M1a,b=x and M2a,b=y. A set of l Latin squares of order m, say M1,…,Ml, are called pairwise orthogonal (mutually orthogonal) Latin squares (MOLS) if Mα and Mβ are orthogonal for all 1≤α<β≤l.Example 2.
(see [3]). Let A=B=1,2,3,4. Then, the encoming Latin squares M1 and M2 are orthogonal.(1)M1=1243342143122134,M2=1432412323413214.
IfH=H1,…,Hm and T=T1,…,Tm are two decompositions of Km,m, then H and T are orthogonal if EHx∩ETy=1 for all x,y∈1,2,…,m. It is clear from the orthogonality that EHx=ETx=m for all x∈1,2,…,m.
Letℤm=1,2,…,m the complete bipartite network Km,m has consisted of two independent sets of vertices, then the first set of the vertices is labeled by Zm×0, and the second set of the nodes is labeled by Zm×1. For any i,j∈Zm, we will use i0 for the vertex i,0 and j1 for the vertex j,1. Consequently, the edge set of Km,m is EKm,m=i0,j1:i,j∈Zm.Definition 3.
(see [3]). Let G be a subgraph of Km,m and the number of its edges be m. Then, a square matrix M with order m is G-square if each element in ℤm=1,2,…,m is found exactly m times in M, and for any x∈Zm, all graphs Gx are isomorphic to G, where EGx=i0,j1:Mi0,j1=x. The set ℤm×0 is used as an index set for the rows of M, and the set Zm×1 is used as an index set for the columns of M. The Latin square of order m is considered a mK2-square.
A set of decompositions {T1,T2, …, Tk} of Km,m is considered a set of k mutually orthogonal graph squares (MOGS) if Tx and Ty are orthogonal for all x,y∈1,2,…,k and x≠y.Figure 1
Three mutually orthogonal decompositions ofK4,4 by 2S2.Example 3.
(see [4]). Figure 1 exhibits three mutually orthogonal decompositions of K4,4 by 2S2. These decompositions can be represented by the following three mutually orthogonal 2S2-squares M1,M2, and M3.(2)M1=4321214343212143,M2=2341321432142341,M3=3412341221432143.
Great efforts have been made for getting the solution of several problems concerned with the MOLS since Euler first asked about MOLS for solving the thirty-six officers’ problem. Bose, Shrikhande, and Parker introduced celebrated theorems concerned with the MOLS [5,6]. Also, Wilson in [7] handled celebrated theorems concerned with the MOLS. For a brief survey on constructions of MOLS, see [8]. El-Shanawany [3] introduced the conjecture, Nq;Pq+1=q, where q is a prime number and Pq+1 is a path on q+1 vertices. The authors in [9] solved this conjecture. In [10], El-Shanawany computed Np;G where G is a graph path. El-Shanawany [11] computed Nn;G=k≥3, where G consists of disjoint union of isomorphic subgraphs of Kn,n. Higazy found Nn;G for all possible subgraphs G with n = 3, 4 edges [12]. The Kronecker product of MOGS was defined in [4] and was applied to construct MOGS for disjoint union of star graphs. El-Shanawany et al. [13] introduced the MOGS for some paths. For more results on MOGS, see [14–18].
Motivated by all previous results, the main aim of this paper is to benefit from the results of MOGS in the literature to construct new structures. These structures are called graph-transversal designs and authentication codes. The decomposition of numerous bipartite graphs, for constructing the studied structures, demonstrates the robustness and the advantages of the suggested techniques. The novelty of the current paper is demonstrated by the fact that it is the first to introduce the transversal designs and authentication codes by MOGS.
The remaining part of the paper is organized as follows: graph-transversal designs by MOGS are introduced in Section2. Section 3 investigates the design of message authentication codes based on MOGS. In Section 4, an application of the graph-transversal design in key predistribution in wireless sensor networks is introduced. Section 5 shows the conclusion.


## 2. Graph-Transversal Designs by MOGS

In this section, we prove that many results of MOGS are equivalent to the transversal designs. Now, we introduce the definition of these objects.Table 2
The blocks and the groups of aTD4,1;3 transversal design.
GroupsBlocksχ1=z11,z12,z13,z14χ2=z11,z22,z23,z24Σ1=z11,z21,z31χ3=z11,z32,z33,z34Σ2=z12,z22,z32χ4=z21,z12,z23,z34Σ3=z13,z23,z33χ5=z21,z22,z33,z14Σ4=z14,z24,z34χ6=z21,z32,z13,z24χ7=z31,z12,z33,z24χ8=z31,z22,z13,z34χ9=z31,z32,z23,z14Definition 2.
Suppose thatm≥2 and n≥1. Then, a transversal design TDm,λ;n is a triple Ζ,Σ,χ, where the encoming properties are verified.(1)
Ζ=zxy,xy∈1,2,…,n×1,2,…,m is a set of mn elements. These elements are called points.(2)
Σ=Σi:1≤i≤m is a partition of Ζ into m subsets. These subsets are called groups; they are not considered algebraic groups. The size of each group is n.(3)
χ is a set of m-subsets of Ζ, which are called blocks.(4)
Every couple of points from different groups is found in preciselyλ blocks in χ, and(5)
Any block and any group have precisely one point in common.Example 4.
The blocks and the groups of aTD4,1;3 transversal design are exhibited in Table 2, where the set Ζ=zxy,xy∈1,2,3×1,2,3,4, Σ=Σ1,Σ2,Σ3,Σ4, and χ=χ1,χ2,…,χ9.
In the following proposition, we prove that if we havek mutually orthogonal G-squares of order n, then we can construct the graph-transversal design G−TDk,1;n. This proposition is followed by some results concerned with the graph-transversal designs by different graph classes.Proposition 1.
If there arek mutually orthogonal G-squares of order n, then there is a graph-transversal design G−TD[k,1;n].Proof.
Let thek mutually orthogonal G-squares of order n are Li, 1≤i≤k. Define Ζ=zxy,xy∈1,2,…,n×1,2,…,k. For 1≤i≤k, consider Σi=zxi:x∈1,2,…,n, and then Σ=Σi:1≤i≤k. For 1≤t≤n2, define χt=zLiλ,t−λ−1ni:1≤i≤k,1≤λ≤n, λ−1n+1≤t≤λn, and χ=χt:1≤t≤n2. Hence, Ζ is a set of kn elements, Σ is a partition of Ζ into k groups, χ is a set of k-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the transversal design TDk,1;n. We call this design a graph-transversal design G−TDk,1;n.Figure 2
Three mutually orthogonal decompositions ofK4,4 by C4.Example 5.
Let the three mutually orthogonalC4-squares with order four are represented by the encoming matrices, see Figure 2.(3)L1=4411441122332233,L2=4141232341412323,L3=4224311331134224.
By applying the previous technique in Proposition1 to convert the three mutually orthogonal C4-squares to C4−TD3,1;4 transversal design, we get Ζ=zxy,xy∈1,2,3,4×1,2,3, and for 1≤i≤3, we have Σi=zxi:x∈1,2,3,4 and Σ=Σi:1≤i≤3. For 1≤t≤16, we have χt=zLiλ,t−λ−1ni:1≤i≤3,1≤λ≤4,4λ−1+1≤t≤4λ, and χ=χt:1≤t≤16. For illustration, see Table 3. In what follows, we will construct some graph-transversal designs based on the ingredients in Table 4 and Proposition 1 which connects between the MOGS and the graph-transversal designs. We present several results such as path-transversal designs, cycle-transversal designs, and disjoint unions of stars-transversal designs.Table 3
The blocks and the groups of aC4−TD3,1;4 transversal design.
χ1=z41,z42,z43χ2=z41,z12,z23χ3=z11,z42,z23χ4=z11,z12,z43χ5=z41,z22,z33χ6=z41,z32,z13Σ1=z11,z21,z31,z41χ7=z11,z22,z13Σ2=z12,z22,z32,z42χ8=z11,z32,z33Σ3=z13,z23,z33,z43χ9=z21,z42,z33χ10=z21,z12,z13χ11=z31,z42,z13χ12=z31,z12,z33χ13=z21,z22,z43χ14=z21,z32,z23χ15=z31,z22,z23χ16=z31,z32,z43Table 4
Some ingredients of MOGS from literature, see [3].
IngredientOrderGraphSquaresk(a)n is a prime >2S1∪n−1/2S2Mi=axyi,axyi=γ,x=δ,y=γ+i−1δ+δ2;γ,δ∈ℤn,i∈1,…,n.n(b)n is a prime >2n−2S1∪S2Mi=axyi,axyi=ix+y−hx,i∈1,…,n−1,hx=1ifx=10otherwisen−1(c)9S3∪3S2Mi=axyi,i∈1,2,3,axyi=δ,x=γ,y=γ2+i−1γ+δ, and γ,δ∈ℤ9.3(d)n is a prime >2Pn+1Mi=axyi,axyi=γ,x=γ+iδ−δ2,y=γ+iδ−δ2;γ,δ,i∈1,…,n.nNote thatk is the number of MOGS.Corollary 1.
Letn be a prime >2. Then, there exists a S1∪n−1/2S2−TDn,1;n.Proof.
Let then mutually orthogonal S1∪n−1/2S2-squares of order n are Mi, 1≤i≤n. Define Ζ=zxy,xy∈1,2,…,n×1,2,…,n. For 1≤i≤n, consider Σi=zxi:x∈1,2,…,n, and then, Σ=Σi:1≤i≤n. For 1≤t≤n2, define χt=zMiλ,t−λ−1ni:1≤i≤n,1≤λ≤n,λ−1n+1≤t≤λn, and χ=χt:1≤t≤n2. Hence, Ζ is a set of n2 elements, Σ is a partition of Ζ into n groups, χ is a set of n-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design S1∪n−1/2S2-TDn,1;n.Corollary 2.
Letn be a prime >2. Then, there exists a n−2S1∪S2-TDn−1,1;n.Proof.
Let then−1 mutually orthogonal n−2S1∪S2-squares of order n are Mi, 1≤i≤n−1. Define Ζ=zxy,xy∈1,2,…,n×1,2,…,n−1. For 1≤i≤n−1, consider Σi=zxi:x∈1,2,…,n, and then, Σ=Σi:1≤i≤n−1. For 1≤t≤n2, define χt=zMiλ,t−λ−1ni:1≤i≤n−1, 1≤λ≤n,λ−1n+1≤t≤λn, and χ=χt:1≤t≤n2. Hence, Ζ is a set of n2−n elements, Σ is a partition of Ζ into n−1 groups, χ is a set of n−1-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design n−2S1∪S2-TDn−1,1;n.Corollary 3.
There exists aS3∪3S2-TD3,1;9.Proof.
Let the3 mutually orthogonal S3∪3S2-squares of order 9 are Mi, 1≤i≤3. Define Ζ=zxy,xy∈1,2,…,9×1,2,3. For 1≤i≤3, consider Σi=zxi:x∈1,2,…,9, and then Σ=Σi:1≤i≤3. For 1≤t≤81, define χt=zMiλ,t−λ−1ni:1≤i≤3,1≤λ≤9,9λ−1+1≤t≤9λ, and χ=χt:1≤t≤81. Hence, Ζ is a set of 27 elements, Σ is a partition of Ζ into 3 groups, χ is a set of 3-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design S3∪3S2-TD3,1;9.Corollary 4.
Letn be a prime >2. Then, there exists a Pn+1-TDn,1;n.Proof.
Let then mutually orthogonal Pn+1-squares of order n are Mi, 1≤i≤n. Define Ζ=zxy,xy∈1,2,…,n×1,2,…,n. For 1≤i≤n, consider Σi=zxi:x∈1,2,…,n, and then Σ=Σi:1≤i≤n. For 1≤t≤n2, define χt=zMiλ,t−λ−1ni:1≤i≤n,1≤λ≤n,λ−1n+1≤t≤λn, and χ=χt:1≤t≤n2. Hence, Ζ is a set of n2 elements, Σ is a partition of Ζ into n groups, χ is a set of n-subsets (blocks) of Ζ, and every couple of points from different groups is found in precisely one block; since M is an orthogonal array, any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design Pn+1-TDn,1;n.Corollary 5.
There exists a C4-TD[3, 1;4].Proof.
Let the3 mutually orthogonal C4-squares of order 4 are Mi, 1≤i≤3. Define Ζ=zxy,xy∈1,2,3,4×1,2,3. For 1≤i≤3, consider Σi=zxi:x∈1,2,3,4, and then, Σ=Σi:1≤i≤3. For 1≤t≤16, define χt=zMiλ,t−λ−1ni:1≤i≤3,1≤λ≤4,4λ−1+1≤t≤4λ, and χ=χt:1≤t≤16. Hence, Ζ is a set of 12 elements, Σ is a partition of Ζ into 3 groups, χ is a set of 3-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design C4−TD3,1;4.Corollary 6.
There exists a2S2−TD3,1;4.Proof.
Let the3 mutually orthogonal 2S2-squares of order 4 are Mi, 1≤i≤3. Define Ζ=zxy,xy∈1,2,3,4×1,2,3. For 1≤i≤3 consider Σi=zxi:x∈1,2,3,4, and then Σ=Σi:1≤i≤3. For 1≤t≤16, define χt=zMiλ,t−λ−1ni:1≤i≤3,1≤λ≤4,4λ−1+1≤t≤4λ and χ=χt:1≤t≤16. Hence, Ζ is a set of 12 elements, Σ is a partition of Ζ into 3 groups, χ is a set of 3-subsets (blocks) of Ζ, every couple of points from different groups is found in precisely one block, and any block and any group have precisely one point in common. Now, the triple Ζ,Σ,χ satisfies the conditions of the graph-transversal design 2S2−TD3,1;4.


## 3. Constructing Graph-Authentication Codes Based on Mutually Orthogonal Graph Squares

Firstly, we retrieve some basic fundamentals of authentication codes. More details on authentication codes can be found in [1, 2].An authentication code is defined as a four tupleA=S,K,T,δ where S,K,T are three nonempty finite sets defined as source states set, keys set, tags set (authenticators set), respectively, and δ:K×S⟶T is the encoding map. The map δ is needed not to be injective, but it should be surjective. For each key σ∈K, there is an authentication rule eσ∈δ, where eσ:S⟶T.The cardinalitiesS,K,T are called the size parameters of the code A. For a specific authentication code A with S,K,T as size parameters, we may describe it as AcS,K,T.LetA=S,K,T,δ be an authentication code. A graph GA induced from A is constructed as follows:(1)
VGA=K∪T(2)
EGA=σ,t|σ∈K,t∈T,∃s∈S such that δs,σ=t(3)
Ifσ,t∈EGA, then such edge has a label s where δs,σ=tThis construction implies that the graphGA is isomorphic to a bipartite graph with partition sets K and T. Moreover, the degree of each vertex in K equals S.The motivation for using authentication codes is usually that the sender and receiver want to have a guarantee that any manipulations of a messages during transit are detected. For this, they randomly choose a private key σ∈K. A source state is simply the information that the sender wants to transmit to the receiver. When the sender needs to transmit the source state s∈S to the receiver, he (or she) uses the authentication rule eσ to construct the tag (authenticator) t=eσs. Then, an authenticated message m is formed by concatenating s and t and then sent over the channel, that is, m=s,t. When the receiver receives m, he or she computes t′=eσs. If t′=t, then the message is accepted as authentic; otherwise, it is rejected.Authentication codes are used in communication channels in which an opponent is present in addition to the sender and the receiver. Such an opponent may play an impersonation attack or substitution attack. Through impersonation attacks, the opponent sends a message over the channel to the receiver and expects that the receiver will authentically accept it. In substitution attack, the opponent watches a message transmitted by the sender, and he replaces this message with another message and wants it to be accepted as authentic from the receiver. For each of these types of attacks, there is an associated probability such that the opponent may succeed to deceive the receiver. LetPI stands for the probability, the opponent will succeed in the impersonation attack, and Ps stands for the probability of a successful substitution attack. For more security, the sender and receiver need to establish an authentication code with small values of PI and Ps.In the following theorem, we prove that mutually orthogonal graph squares MOGS can be used to construct an authentication code withPI=Ps=1/T. We call this special code a graph authentication codeG−AcS,K,T.Figure 3
The induced graph of the codeC4−Ac3,16,4.Theorem 1.
Suppose there arek mutually orthogonal graph squares MOGS L1,L2,…,Lk each of order n. The entries of any Li|1≤i≤k are elements of Zn. Then, there is a graph authentication code G−AcS,K,T with K=n2,S=k,T=n, and PI=Ps=1/n.Proof.
Claim 1: Mutually orthogonal graph squares Li|1≤i≤k can be reduced to a graph-authentication code A=S,K,T,δ as follows: let S=k, K=n2, and T=ℤn. For any si∈S, and σj∈K,1≤j≤n2, set δσj,si=Lix,y, and(4)x,y=1,jif1≤j≤n2,j−nifn+1≤j≤2n3,j−2nif2n+1≤j≤3n⋮⋮⋮n,j−n2+nifn2−n≤j≤n2.Lix,y is the element in the cell x,y of the graph squares Li. Formula (4) is equivalent to eσjsi=Lix,y=t∈ℤn. Consequently, each t∈T occurs exactly n times in each graph square, and then, the map δ is surjective. Hence, this reduction yields to an authentication code A=S,K,T,δ.Claim 2: Here, we will compute the probability PI. Suppose that an opponent transmits any message m=si,t into the channel. Then, m is accepted as authentic if and only if t=eσjsi, which occurs if and only if δσj,si=t. Since σj chosen randomly, it is only known to the sender and the receiver but not by the opponent. Let ρsi,t=σj:δσj,si=t. Since our code constructed from mutually orthogonal graph squares of order n, then each entry occurs exactly n times in each square. Following formula (4), it is easy to see that ρsi,t=n, and opponent’s deception will succeed if and only if σj∈ρsi,t. Since K=n2, it yields that the opponent will succeed to deceive the receiver with probability ρsi,t/K=1/n. Since this probability is independent of the message m=si,t that opponent submits into the channel, so(5)PI=1n.Claim 3: The second probability that we will compute is the substitution probability Ps. Suppose that an opponent observes an authentic message m=si,t passing the channel. He or she changes it to another message m′=si′,t′ where si≠si′ and desires that the receiver will accept it. As we have done in PI, let ρsi,t=σj:δσj,si=t. Since the opponent is able to see the message m, this makes it easy for him or her to guess that σj∈ρsi,t. This means that the number of expected keys is reduced to n. The opponent will deceive the receiver if and only if σj∈ρsi′,t′. As it is known to the opponent that σj∈ρsi,t, then the private key σj satisfies that σj∈ρsi′,t′∩ρsi,t. This code is constructed from mutually orthogonal graph squares of order n. Consequently, for any two of such squares, that is, Lu and Lv and for every t∈Zn and every t′∈ℤn, there is a unique cell x,y such that Lux,y=t and Lvx,y=t′. Hence, we conclude that ρsi′,t′∩ρsi,t=1. Till now, it is known to the opponent that σj∈ρsi,t, and he or she will succeed if and only if σj∈ρsi′,t′∩ρsi,t. Therefore, the probability of a successful substitution attack is(6)Ps=ρsi′,t′∩ρsi,tρsi,t=1n.Lemma 1.
There exists aC4−Ac3,16,4 with PI=Ps=1/4.Proof.
Let the 3 mutually orthogonalC4-squares of the order 4 be Mi, 1≤i≤3 listed in Table 4. Define an authentication code with three sources states s1,s2,s3. The key set K=σj:1≤j≤16. For each pair σj,si, use formula (4) to set δσj,si. The induced graph of this reduction is shown in Figure 3. By straightforward application of Theorem 1, the code is constructed from mutually orthogonal C4-squares of the order 4 has PI=Ps=1/4.


## 4. Applications of the Graph-Transversal Designs in Key Predistribution in Wireless Sensor Network

The balance of key content in different sensor nodes can be achieved by combinatorial design [19]; the maximum number of couples of nodes may communicate directly by a pairwise common key. The transversal design is a combinatorial design that can introduce a deterministic nature of key distribution [20]. In [21], the authors proposed the application of transversal design in key predistribution in wireless sensor networks. Now, we introduce an example to show the application of the graph-transversal designs. From Example 3, we can construct the 2S2−TD3,1;4 transversal design as shown in Table 5.Table 5
The blocks and the groups of a2S2−TD3,1;4 transversal design.
χ1=z41,z22,z33χ2=z31,z32,z43χ3=z21,z42,z13χ4=z11,z12,z23χ5=z21,z32,z33χ6=z11,z22,z43Σ1=z11,z21,z31,z41χ7=z41,z12,z13Σ2=z12,z22,z32,z42χ8=z31,z42,z23Σ3=z13,z23,z33,z43χ9=z41,z32,z23χ10=z31,z22,z13χ11=z21,z12,z43χ12=z11,z42,z33χ13=z21,z22,z23χ14=z11,z32,z13χ15=z41,z42,z43χ16=z31,z12,z33In Table5, each block represents the key ids of a certain node in a sensor network. The numbers in the blocks represent the set of key ids. Here, the common key between blocks χ4 and χ6 is z11. The maximum number of shared key between two nodes is 1 in the transversal design. Consequently, it may happen that there is no shared key between two nodes. For instance, nodes 1 and 2 have not any common key. Therefore, if they want to communicate, they need one or more intermediate nodes. In Table 5, the block χ5 has a common key with both the blocks χ1 and χ2. Hence, blocks χ1 and χ2 can communicate through block χ5 by key z33 and z32, respectively.Now, we can construct a wireless sensor network of 16 nodes corresponding to the2S2−TD3,1;4 as shown in Figure 4 such that there is a link between two nodes if there is a common key between them.Figure 4
Wireless sensor network of 16 nodes corresponding to the 2S2 − TD[3, 1; 4].


## 5. Conclusion

The importance of combinatorial design theory can be attributed in large degree to its continued deep interactions with algebra, geometry, and number theory and its applications in communications and coding theory. Combinatorial design theory is mature and rich in wide practical applications today. The paper you hold in your hands presents a seamless interaction of mutually orthogonal graph squares (MOGS), graph-transversal designs, and authentication codes. MOGS is the generalization of the mutually orthogonal Latin squares used for constructing the transversal designs; hence, the MOGS helps us to construct new interesting graph-transversal designs and authentication codes. The paper’s novelty is demonstrated by the fact that it is the first to construct graph-transversal designs and graph-authentication codes based on MOGS concerned with complete bipartite graphs. We will strive to enhance the existing methods and propose new algorithms in the future to make them applicable for all classes of graphs that can be used to construct new graph-transversal designs and graph-authentication codes.



---

*Source: 8992934-2022-05-29.xml*