|
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
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
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
Linking options:
https://www.mathnet.ru/eng/dm979https://doi.org/10.4213/dm979 https://www.mathnet.ru/eng/dm/v19/i4/p97
|
Statistics & downloads: |
Abstract page: | 728 | Full-text PDF : | 372 | References: | 65 | First page: | 11 |
|