Pseudo orthogonal Latin squares (Q1996840)

The authors prove that the existence of a family of \(m\) mutually pseudo orthogonal Latin squares of order \(n\) (\(\mathrm{POLS}(m;n)\)) is equivalent to the existence of a family of \(m\) mutually orthogonal Latin squares of order \(n\) (\(\mathrm{MOLS}(m;n)\)). Two distinct Latin squares \(A\), \(B\) of order \(n\) are said to be pseudo orthogonal if for each \(1\leq i\), \(j\leq n\) there is a \(k\) with \(1\leq k\leq n\) satisfying \(A(i,k)=B(j,k)\). The notion of pseudo orthogonality was first introduced in [\textit{N. S. Bolshakova}, Discrete Math. Appl. 18, No. 2, 187--197 (2008; Zbl 1200.05141); translation from Diskretn. Mat. 20, No. 1, 70--79 (2008)]. The authors use graph invariants to establish a relationship between pseudo orthogonal Latin squares and orthogonal Latin squares. Specifically, for a graph \(G\), these invariants are the clique partition number of \(G\) and the size \(\pi (G)\) of a prime set for an optimum \(\pi\)-labeling of \(G\). For \(m\geq 0\) and \(n\geq 2\) let \(G\) be the graph obtained by taking the union of \(m+2\) vertex disjoint complete graphs on \(n\) vertices. The authors' theorem asserting the equivalence of a family of \(\mathrm{MOLS}(m;n)\) and a family of \(\mathrm{POLS}(m;n)\) also has two intermediate equivalent statements: (1) \(\pi (G)=n^2\) and (2) there is a clique partition of \(\bar G\) which consists only of \(K_{m+2}\)'s. The authors apply this theorem and surrounding ideas to obtain exact values of clique partition numbers of several classes of complete multipartite graphs and tensor products of complete graphs.