# When can any graph $G$ be expressed as a union of $\alpha(G)$ complete graphs?

If for any graph $$H$$ we define $$\alpha(H)$$ to be the cardinality of any maximum size indepedent set in $$H$$. Then under what conditions can any graph $$G$$ be expressed as a union of $$\alpha(G)$$ complete graphs?

Or equivalently if $$[S]_2$$ is the set of all two element subsets of $$S$$, then for which class of graphs $$G$$ will there exist $$\alpha(G)$$ sets $$V_{1},V_2,\ldots V_{\alpha(G)}$$ that satisfy $$V(G)=\bigcup_{n=1}^{\alpha(G)}V_n$$ and $$E(G)=\bigcup_{n=1}^{\alpha(G)}[V_n]_2$$?

Are there any reasonably simple necessary and sufficient conditions for categorizing these graphs?

Lastly also note if there are $$n$$ complete graphs $$C_1,C_2,\ldots C_n$$ with $$G=\bigcup_{k=1}^n C_k$$ and $$n<\alpha(G)$$ there must exist an independent set $$I$$ of $$G$$ such that $$|I|=n+1$$ however by assumption we have that $$I\subseteq V(G)=\bigcup_{k=1}^nV(C_k)$$ therefore by the pigeonhole principal there must exists two distinct vertices $$u,v\in V(C_j)$$ for some integer $$1\leq j\leq n$$ yet since $$V(C_j)$$ is a clique of $$G$$ this means we have $$\{u,v\}\in E(G)$$ contradicting the fact $$I$$ is an independent set of $$G$$, which proves $$n\geq \alpha(G)$$. Thus a a corollary if we let $$\theta(G)$$ be the intersection number of $$G$$ then by definition we have that:

$$G\text{ is a union of }\alpha(G)\text{ complete graphs}\iff \alpha(G)=\theta(G)$$

However I'm unable to simplify these equivalent conditions into anything nice either.

• Do you have an example showing it's a proper subclass of this class? What is the context in which this question is asked? Commented Mar 16, 2019 at 9:33
• @Carl-FredrikNybergBrodda I don't understand your trees example. $\alpha(G)$ can be as small as $n/2$ but $n-1$ cliques are needed to cover the edges. Commented Mar 17, 2019 at 0:52
• What does "$G$ is a union of complete graphs" mean? I would have thought that every (simple) graph is a union of complete graphs. What is an example of a graph which is not a union of complete graphs?
– bof
Commented Mar 17, 2019 at 4:04
• @bof I made a slight error and was referring to complete graphs on three or more vertices I reverted it. Commented Mar 17, 2019 at 4:50

## 2 Answers

I don't think there is a pretty answer to this question. A graph is in this class iff it is the union of a set of cliques such that each of the cliques has a vertex not in any of the other cliques.

Given a maximum independent set $$S$$, you can identify said cliques as the closed neighbourhoods of the vertices in $$S$$. Conversely given such a set of cliques, the special vertices are a maximum independent set.

I know I already accepted an answer nine months ago, though these came up again in a problem I was working on involving digraph Kernels and upon further investigation these are actually called "bound graphs" as a matter of fact we have the following chain of equivalences: $$G\text{ is a bound graph}\iff\alpha(G)=\theta(G)\iff \vartheta(G)=\theta(G)\\\iff\text{For all spanning subgraphs }H\text{ of }G\text{ we have }\theta(H)\geq\theta(G)\\\iff \text{For all subgraphs }H\text{ of }G\text{ we have }\theta(H)\geq \theta(G[V(H)])$$

Thus the property of being a "bound graph" is hereditary which means for any bound graph $$G$$ we see every induced subset $$H$$ of $$G$$ is a bound graph and therefore note for every induced subset $$H$$ of $$G$$ we have the identity $$\alpha(H)=\theta(H)=\vartheta(H)$$ though this means every induced subgraph $$H$$ of $$G^{\complement}$$ satisfies $$\chi(H)=\omega(H)$$ thus $$G^{\complement}$$ must be a perfect graph which by the Perfect graph theorem this means $$G$$ is a perfect graph. Thus this proves bound graphs are a particular class of perfect graphs.