RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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.

DOI: https://doi.org/10.4213/dm990

Full text: PDF file (140 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 519.15
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

Citation in format AMSBIB
\Bibitem{Bol08}
\by N.~S.~Bol'shakova
\paper The intersection number of complete $r$-partite graphs
\jour Diskr. Mat.
\yr 2008
\vol 20
\issue 1
\pages 70--79
\mathnet{http://mi.mathnet.ru/dm990}
\crossref{https://doi.org/10.4213/dm990}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2420498}
\zmath{https://zbmath.org/?q=an:05618976}
\elib{http://elibrary.ru/item.asp?id=20730230}
\transl
\jour Discrete Math. Appl.
\yr 2008
\vol 18
\issue 2
\pages 187--197
\crossref{https://doi.org/10.1515/DMA.2008.015}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44449153907}


Linking options:
  • http://mi.mathnet.ru/eng/dm990
  • https://doi.org/10.4213/dm990
  • http://mi.mathnet.ru/eng/dm/v20/i1/p70

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Number of views:
    This page:336
    Full text:112
    References:24
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020