Pseudo orthogonal Latin squares

DOI10.1515/DMA-2021-0002MaRDI QIDQ1996840zbMATH OpenOpenAlexWikidataFDO

Authors Shahab Faruqi, S. A. Katre, Manisha Garg

Publication date 26 February 2021

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2021-0002

zbMATH Keywords

\(\pi\) labelingclique partition numbersmutually orthogonal Latin squaresmutually pseudo orthogonal Latin squares

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

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.

Recommendations

• The intersection number of complete r-partite graphs
• Difference covering arrays and pseudo-orthogonal Latin squares
• scientific article; zbMATH DE number 894713
• scientific article; zbMATH DE number 2094526
• The search for pseudo orthogonal Latin squares of order six

Cites work

• An application of sum composition: a self orthogonal latin square of order ten
• Coprime index of a graph
• Edge-clique covers of the tensor product
• Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's Conjecture
• scientific article; zbMATH DE number 6473829 (Why is no real title available?)
• scientific article; zbMATH DE number 1096962 (Why is no real title available?)
• scientific article; zbMATH DE number 1455120 (Why is no real title available?)
• The intersection number of complete r-partite graphs
• The Representation of a Graph by Set Intersections

Cited in

(6)

• Outline symmetric Latin squares
• The intersection number of complete r-partite graphs
• scientific article; zbMATH DE number 894713 (Why is no real title available?)
• The search for pseudo orthogonal Latin squares of order six
• Mutually orthogonal Latin squares as group transversals
• $k$-однородные латинские квадраты, их трансверсали и условие псевдоортогональности;$k$-homogeneous Latin Squares, their transversals and condition of pseudo-orthogonality

This page was built for publication: Pseudo orthogonal Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996840)