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

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


Diskretnaya Matematika, 2007, Volume 19, Issue 4, Pages 97–107
DOI: https://doi.org/10.4213/dm979
(Mi dm979)
 

This article is cited in 1 scientific paper (total in 1 paper)

On the intersection number of a graph

E. E. Marenich, N. S. Bol'shakova
Full-text PDF (139 kB) Citations (1)
References:
Abstract: We find an expression of the intersection number of a graph in terms of the minimum number of complete subgraphs that form a covering of the graph. This provides us with a uniform approach to studying properties of the intersection number of a graph. We distinguish the class of graphs for which the intersection number is equal to the least number of cliques covering the graph. It is proved that the intersection number of a complete $r$-partite graph $r\overline K_2$ is equal to the least $n$ such that $r\le\binom{n-1}{[n/2]-1}$. It is proved that the intersection number of the graph $r\overline K_2+K_m$ is equal to the least $n$ such that $m+r\le2^{n-1}$, $r\le\binom{n-1}{[n/2]-1}$. Formulas for the intersection numbers of the graphs $rC_4$, $r\operatorname{Chain}(3)$, $r(C_4+K_m)$, $rW_5$ are obtained.
Received: 19.04.2005
English version:
Discrete Mathematics and Applications, 2007, Volume 17, Issue 6, Pages 607–617
DOI: https://doi.org/10.1515/dma.2007.045
Bibliographic databases:
UDC: 519.15
Language: Russian
Citation: E. E. Marenich, N. S. Bol'shakova, “On the intersection number of a graph”, Diskr. Mat., 19:4 (2007), 97–107; Discrete Math. Appl., 17:6 (2007), 607–617
Citation in format AMSBIB
\Bibitem{MarBol07}
\by E.~E.~Marenich, N.~S.~Bol'shakova
\paper On the intersection number of a~graph
\jour Diskr. Mat.
\yr 2007
\vol 19
\issue 4
\pages 97--107
\mathnet{http://mi.mathnet.ru/dm979}
\crossref{https://doi.org/10.4213/dm979}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2392698}
\zmath{https://zbmath.org/?q=an:05233566}
\elib{https://elibrary.ru/item.asp?id=9917190}
\transl
\jour Discrete Math. Appl.
\yr 2007
\vol 17
\issue 6
\pages 607--617
\crossref{https://doi.org/10.1515/dma.2007.045}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-37049033902}
Linking options:
  • https://www.mathnet.ru/eng/dm979
  • https://doi.org/10.4213/dm979
  • https://www.mathnet.ru/eng/dm/v19/i4/p97
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:728
    Full-text PDF :372
    References:65
    First page:11
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024