The maximum number of cliques in dense graphs (Q1061136)

We will consider only undirected, connected graphs without loops or multiple edges. Denote the number of vertices of G by \(| G|\). A clique of graph G is a maximal complete subgraph. The clique graph K(G) of G is the intersection graph of the cliques of G. The density w(G) is the number of vertices in the largest clique of G. A graph is called dense if w(G)\(\geq | G| /2.\) This paper makes precise the intuitive idea that very dense graphs have fewer cliques than less dense graphs. First, it is shown that for any graph G, \(2^{| G| -w(G)}\geq | K(G)|.\) Secondly, this bound is sharp among dense graphs, and among them only. In fact, for all integers s,t\(\geq 4\) where \(t\geq s\geq t/2\), there exists a graph G such that \(| G| =t\), \(w(G)=s\), and \(2^{t-s}=| K(G)|.\) Call a dense graph packed if \(2^{| G| -w(G)}=| K(G)|.\) The 2n- Neumann graph is the complement of a matching between 2n vertices. Thirdly, it is shown that any packed graph G contains an induced subgraph isomorphic to the 2[\(| G| -w(G)]\)-Neumann graph. Lastly, the clique graphs of packed graphs are characterized.