Isotopy graphs of Latin tableaux (Q2048368)

In this paper, the authors extend the notion of isotopism from Latin squares to Latin tableaux. Then, they introduce the concept of isotopy graph \(\mathcal{G}(\lambda)\) as a graph whose vertices are Latin tableaux of a given shape \(\lambda\), so that two vertices are adjacent if and only if their corresponding Latin tableaux are isotopic. That is, they coincide up to permutation of rows, columns or entries. Moreover, the isotopy graph of a Latin tableau \(T\) of shape \(\lambda\) is the connected component of \(\mathcal{G}(\lambda)\) containing \(T\). Particularly, the existence of a Latin tableau whose isotopy graph is isomorphic to a \(d\)-dimensional cube is proved, whatever the positive integer \(d\) is. In addition, the set of Latin tableaux having cubes as their isotopy graphs is characterized. Furthermore, it is proved that the majority of isotopy graphs are triangle-free and that any of the connected component of an isotopy graph is regular. The authors also characterize those Latin tableaux whose isotopy graph contains a triangle. Concerning the structure of isotopy graphs, it is proved that the clique number of an isotopy graph is either 1, 2 or 4. In fact, the majority of isotopy graphs are proved to have clique number two. Finally, a formula is established for the degree of each vertex of a given isotopy graph. It depends on both the shape of the tableau and the filling.