5
$\begingroup$

Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$: there are $\Theta(n^2)$ edges and each clique can cover at most $O(n)$ edges, so the lower bound for the complete subgraph size is $\Omega\left(\sqrt{\frac{n^2}{n}}\right)=\Omega\left(\sqrt{n}\right)$. This lower bound is also tight: we can partition vertices into $\sqrt{n}$ sets with $\sqrt{n}$ nodes in each set, and any pair of sets form a complete subgraph.

I want to ask for a generalization of the above question when the graph is not a complete graph: when the graph has $m$ edges, is it always possible to cover the graph by $n$ cliques with size $\sqrt{\frac{m}{n}}$? (the clique can contain non-edge). To be precise, I want to find the smallest possible $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ and every edge $(u,v)$ has $u,v$ both contained in some $S_i$.

I searched for clique edge covering but most of the results only consider the case where cliques cannot cover non-edge. I wonder if there exists any similar research in the setting when cliques can cover non-edge.

Improve this question
$\endgroup$
4
  • $\begingroup$ In the definition, don't you want $S_1,\ldots,s_\ell$ to be cliques? $\endgroup$
    – Christophe Leuridan
    Commented Jan 31, 2023 at 18:47
  • $\begingroup$ $S_1,S_2,...,S_n$ are vertex sets. In the definition I want for any edge $(u,v)$ we have $u,v\in S_i$ for some $i\in[n]$. This is another way to say we want to use $n$ cliques to cover all the edges. $\endgroup$
    – walydna
    Commented Jan 31, 2023 at 19:03
  • $\begingroup$ It seems that if G has a large girth, then coverings with small cliques will be inefficient (will contain many "non-edges"). Maybe this provides examples where $\sqrt{m/n}$ cliques are not enough? $\endgroup$
    – Ivan Izmestiev
    Commented Jan 31, 2023 at 19:55
  • $\begingroup$ The way you are using the term clique is non-standard. I suggest changing the title to something like covering the edges of a graph with small subgraphs. $\endgroup$
    – Tony Huynh
    Commented Feb 1, 2023 at 8:06

1 Answer 1

Reset to default
5
$\begingroup$

Here is an example showing that the clique size $\sqrt{m/n}$ does not suffice.

Graphs on $n$ vertices without 4-cycles have less than $O(n^{3/2})$ edges, and there is a series of examples where this asymptotic bound is attained. If one wishes to cover all edges of such a dense graph with $n$ cliques of equal size, then these cliques must contain $\Theta(n^{1/2})$ edges on average, and are still 4-cycle-free. Thus the clique size is at least $n^{1/3}$, while $\sqrt{m/n} = \Theta(n^{1/4})$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.