Balanced equi-\(n\)-squares

Saieed Akbari ; Trent G. Marbach ; Rebecca J. Stones ; Zhuanhao Wu

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

We define a $d$-balanced equi-$n$-square $L=(l_{ij})$, for some divisor $d$ of $n$, as an $n \times n$ matrix containing symbols from $\mathbb{Z}_n$ in which any symbol that occurs in a row or column, occurs exactly $d$ times in that row or column. We show how to construct a $d$-balanced equi-$n$-square from a partition of a Latin square of order $n$ into $d \times (n/d)$ subrectangles. In graph theory, $L$ is equivalent to a decomposition of $K_{n,n}$ into $d$-regular spanning subgraphs of $K_{n/d,n/d}$. We also study when $L$ is diagonally cyclic, defined as when $l_{(i+1)(j+1)}=l_{ij}+1$ for all $i,j \in \mathbb{Z}_n$, which correspond to cyclic such decompositions of $K_{n,n}$ (and thus $\alpha$-labellings). We identify necessary conditions for the existence of (a) $d$-balanced equi-$n$-squares, (b) diagonally cyclic $d$-balanced equi-$n$-squares, and (c) Latin squares of order $n$ which partition into $d \times (n/d)$ subrectangles. We prove the necessary conditions are sufficient for arbitrary fixed $d \geq 1$ when $n$ is sufficiently large, and we resolve the existence problem completely when $d \in \{1,2,3\}$. Along the way, we identify a bijection between $\alpha$-labellings of $d$-regular bipartite graphs and what we call $d$-starters: matrices with exactly one filled cell in each top-left-to-bottom-right unbroken diagonal, and either $d$ or $0$ filled cells in each row and column. We use $d$-starters to construct diagonally cyclic $d$-balanced equi-$n$-squares, but this also gives new constructions of $\alpha$-labellings.

Détail

DOI : 10.37236/9118

Classification : 05B15, 05C51, 05C78
Mots-clés : \(\alpha\)-labellings, \(d\)-regular bipartite graphs, \(d\)-starters