Lower bound on weighted clique covering number?

Question

Given an $n$-vertex graph $G$ and assume the largest clique in it has no more than $k(n)$ vertices, where $k(n)\to \infty$ as $n\to\infty$. A clique cover is a collection $\mathcal{S}$ of cliques in $G$ so that $$E(G)\subseteq \cup_{S\in\mathcal{S}}E(S).$$

The weighted clique covering number of $G$ is $$\min_{\mathcal{S} \text{ is a clique cover of $G$}}\sum_{S\in \mathcal{S}}|V(S)|.$$

I am wondering if $\Omega(|E(G)|/k)$ is a lower bound on the clique covering number, as $n\to\infty$?

Answer 1

Assume $S_1,...,S_t$ form the minimum clique cover of $G$ and assume $k_i=|V(S_i)|$ for $1\le i\le t$. As $E(G)\subseteq\cup_{1\le i\le t}E(S_i)$, we have $$\sum_{i=1}^t\binom{k_i}{2}\ge |E(G)|.$$

Then we have $$\text{weighted clique cover number}=\sum_{i=1}^tk_i\ge \sum_{i=1}^{t}\frac{\binom{k_i}{2}}{k_i}\ge \frac{\sum_{i=1}^t\binom{k_i}{2}}{k}\ge\frac{|E(G)|}{k},$$ where $k$ is the maximum order of clique in $G$.

Answer 2

There is definitely such a lower bound.

A clique with $v$ vertices has at most $v(v-1)/2 \le v(k-1)/2$ edges. Therefore, if a set of cliques has total weight $w$ (that is, the orders of the cliques sum to $w$), then those cliques can cover at most $w(k-1)/2$ edges.

If a set of cliques is a clique cover, then those cliques cover all $|E(G)|$ edges, and therefore $$ w(k-1)/2 \ge |E(G)| \implies w \ge 2|E(G)|/(k-1) \ge 2|E(G)|/k. $$ That's true for any clique cover, and therefore the weighted clique covering number also has the same lower bound.