×

zbMATH — the first resource for mathematics

On the order and the number of cliques in a random graph. (English) Zbl 0937.05067
Summary: A clique of a graph \(G\) is a complete subgraph of \(G\) maximal under inclusion. We study the numbers of cliques of various orders in a random graph \(G_{n,p}\) and prove that almost all cliques of \(G_{n,p}\) have the same order, which is approximately \(\log n -\log \log \log n\), where log means the logarithm to the base \(1/p\), and estimate the total number of cliques in \(G_{n,p}\).

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] BOLLOBÁS B.: Random Graphs. Academic Press, New York, 1985. · Zbl 0592.05052
[2] BOLLOBÁS B.-ERDŐS P.: Cliques in random graphs. Math. Proc. Cambridge Philos. Soc. 80 (1976), 419-427. · Zbl 0344.05155 · doi:10.1017/S0305004100053056
[3] FARBER M.-HUJTER M., TUZA, ZS.: An upper bound on the number of cliques in a graph. Networks 23 (1993), 207-210. · Zbl 0777.05070 · doi:10.1002/net.3230230308
[4] FÜREDI Z.: The number of maximal independent sets in connected graphs. J. Graph Theory 11 (1987), 463-470. · Zbl 0647.05032 · doi:10.1002/jgt.3190110403
[5] HEDMAN B.: The maximum number of cliques in dense graphs. Discrete Math. 54 (1985), 161-166. · Zbl 0569.05029 · doi:10.1016/0012-365X(85)90077-9
[6] KALBFLEISCH J. G.: Complete subgraphs of random hypergraphs and bipartite graphs. Proc. of 3rd Southeastern Conference on Combinatorics, Graph Theory and Computing, Florida Atlantic University, 1972, pp. 297-304. · Zbl 0272.05126
[7] KORSHUNOV A. D.: The basic properties of random graphs with large numbers of vertices and edges. Uspekhi Mat. Nauk 40 (1985), 107-173. · Zbl 0574.60015
[8] MATULA D. W.: On the complete subgraphs of a random graph. Proc. 2nd Chapel Hill Conf. Combinatorial Math, and its Applications (R. C. Bose et al., Univ. North Carolina, Chapel Hill, 1970, pp. 356-369. · Zbl 0209.28101
[9] MATULA D. W.: The employee party problem. Notices Amer. Math. Soc. 19 (1972), A-382.
[10] MATULA D. W.: The largest clique size in a random graph. Technical report CS 7608, Dept. of Computer Science, Southern Methodist University, Dallas, 1976.
[11] MOON J. W.-MOSER L.: On cliques in graphs. Israel J. Math. 3 (1965), 22-28. · Zbl 0144.23205 · doi:10.1007/BF02760024
[12] PALMER E. M.: Graphical Evolution: An Introduction to the Theory of Random Graphs. John Wiley, New York, 1985. · Zbl 0566.05002
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.