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

Diskr. Mat., 2007 Volume 19, Issue 4, Pages 97–107 (Mi dm979)

This article is cited 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.

UDC: 519.15

Received: 19.04.2005

DOI: 10.4213/dm979


 English version:
Discrete Mathematics and Applications, 2007, 17:6, 607–617

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024