On the intersection number of a~graph

E. E. Marenich ; N. S. Bol'shakova

Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 97-107

Résumé

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.