zbMATH — the first resource for mathematics

The maximum number of cliques in dense graphs. (English) Zbl 0569.05029
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.

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Billionnet, A, An upper bound on the size of the largest cliques in a graph, J. graph theory, 5, 165-169, (1981) · Zbl 0467.05052
[2] Bollobas, B; Erdös, P, Cliques in random graps, (), 419-427 · Zbl 0344.05155
[3] Chvátal, V, Determining the stability number of a graph, SIAM J. comput., 6, 643-662, (1977) · Zbl 0395.05047
[4] Escalante, F, Über iterierte clique-graphen, Abh. math. sem. univ. Hamburg, 39, 59-68, (1973) · Zbl 0266.05116
[5] Harary, F, Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[6] Harary, F; Lempel, A, On clique-extremal (p, q) graphs, Networks, 4, 371-378, (1974) · Zbl 0309.05125
[7] B. Hedman, Another extremal problem for Turan graphs, forthcoming. · Zbl 0629.05041
[8] Moon, J.W; Moser, L, On cliques in graphs, Israel J. math., 3, 23-28, (1965) · Zbl 0144.23205
[9] Roman, S, The maximum number of q-cliques in a graph with no p-clique, Discrete math., 14, 365-371, (1976) · Zbl 0319.05126
[10] Spencer, J.H, On cliques in graphs, Israel J. math., 9, 419-421, (1971) · Zbl 0209.55201
[11] Turan, P, On the theory of graphs, Colloq. math., 3, 19-30, (1954) · Zbl 0055.17004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.