The intersection number of complete $r$-partite graphs

N. S. Bol'shakova

Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 70-79

Résumé

Latin squares $C,D$ of order $n$ are called pseudo-orthogonal if any two rows of the matrices $C$ and $D$ have exactly one common element. We give conditions for existence of families consisting of $t$ pseudo-orthogonal Latin squares of order $n$. It is proved that the intersection number of a complete $r$-partite graph $r\overline K_n$ equals $n^2$ if and only if there exists a family consisting of $r-2$ pairwise pseudo-orthogonal Latin squares of order $n$. It is proved that if $2\leq r\leq\operatorname{prols}(n,t)+2$, $0\leq m\leq2^{n^2-n}$, where $\operatorname{prols}(n)$ is the maximum $t$ such that there exists a set of $t$ pseudo-orthogonal Latin squares of order $n$, then the intersection number of the graph $r\overline K_n+K_m$ is equal to $n^2$. Applications of the obtained results to calculating the intersection number of some graphs are given.