RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2008 Volume 20, Issue 1, Pages 70–79 (Mi dm990)

This article is cited in 2 papers

The intersection number of complete $r$-partite graphs

N. S. Bol'shakova


Abstract: 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.

UDC: 519.15

Received: 19.04.2005

DOI: 10.4213/dm990


 English version:
Discrete Mathematics and Applications, 2008, 18:2, 187–197

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024