|
This article is cited in 2 scientific papers (total 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.
Received: 19.04.2005
Citation:
N. S. Bol'shakova, “The intersection number of complete $r$-partite graphs”, Diskr. Mat., 20:1 (2008), 70–79; Discrete Math. Appl., 18:2 (2008), 187–197
Linking options:
https://www.mathnet.ru/eng/dm990https://doi.org/10.4213/dm990 https://www.mathnet.ru/eng/dm/v20/i1/p70
|
Statistics & downloads: |
Abstract page: | 469 | Full-text PDF : | 211 | References: | 33 | First page: | 5 |
|