| Autor: |
Davoodi, Akbar, Gerbner, Dániel, Methuku, Abhishek, Vizer, Máté |
| Rok vydání: |
2018 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
A clique covering of a graph $G$ is a set of cliques of $G$ such that any edge of $G$ is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number $scc(G)$ of a graph $G$, is defined as the smallest possible weight of a clique covering of $G$. Let $ K_t(d) $ denote the complete $ t $-partite graph with each part of size $d$. We prove that for any fixed $d \ge 2$, we have $$\lim_{t \rightarrow \infty} scc(K_t(d))= \frac{d}{2} t\log t.$$ This disproves a conjecture of Davoodi, Javadi and Omoomi. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
