Geodesic
On the intersection number of a graph
Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 97-107 
E. E. Marenich; N. S. Bol'shakova. On the intersection number of a graph. Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 97-107. http://geodesic.mathdoc.fr/item/DM_2007_19_4_a5/
@article{DM_2007_19_4_a5,
     author = {E. E. Marenich and N. S. Bol'shakova},
     title = {On the intersection number of a~graph},
     journal = {Diskretnaya Matematika},
     pages = {97--107},
     year = {2007},
     volume = {19},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_4_a5/}
}
TY  - JOUR
AU  - E. E. Marenich
AU  - N. S. Bol'shakova
TI  - On the intersection number of a graph
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 97
EP  - 107
VL  - 19
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_4_a5/
LA  - ru
ID  - DM_2007_19_4_a5
ER  - 
%0 Journal Article
%A E. E. Marenich
%A N. S. Bol'shakova
%T On the intersection number of a graph
%J Diskretnaya Matematika
%D 2007
%P 97-107
%V 19
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2007_19_4_a5/
%G ru
%F DM_2007_19_4_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[2] Szpilrajn-Marczewski E., “Sur deux propriétés des classes d'ensembles”, Fundam. Math., 33 (1945), 303–307 | MR | Zbl

[3] Erdős P., Goodman A. W., Pósa L., “The representation of a graph by set intersections”, Canad. J. Math., 18:1 (1966), 106–112 | MR | Zbl

[4] Scheinerman E. R., Trenk A. N., “On the fractional intersection number of graph”, Graph Comb., 15:3 (1999), 341–351 | DOI | MR | Zbl

[5] Marenich E. E., “Chislo peresechenii grafa”, Materialy VIII Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya”, MGU, Moskva, 2004, 216–219

[6] Bollobás B., Erdős P., Spencer J., West D. B., “Clique covering of the edges of a random graph”, Combinatorica, 13 (1993), 1–5 | DOI | MR | Zbl

[7] Frieze A., Reed B., “Covering the edges of a random graph by cliques”, Combinatorica, 15 (1995), 489–497 | DOI | MR | Zbl

[8] Schönheim J., “On a problem of Purdy related to Sperner systems”, Canad. Math. Bull., 17 (1974), 135–136 | MR | Zbl