zbMATH — the first resource for mathematics

Another extremal problem for Turan graphs. (English) Zbl 0629.05041
Let K(G) and \(\omega\) (G) be the clique graph and clique number of a graph G. For \(1<r<n\), let \(F(n,r)=\max_{G}\{| K(G)|:| V(G)| =n\) and \(\omega (G)=r\}\). A Turan graph \(T(n,r)\) is a multipartite graph with vertices \(v_ 1,v_ 2,...,v_ n\), and \(v_ iv_ j\in E(G)\) if and only if \(i\neq j\) (mod r). Theorem: Let G be a graph of order n with \(\omega (G)=r<n\). Then \(| K(G)| =F(n,r)\) if and only if \(G\sim T(n,r)\).
Reviewer: S.F.Kapoor

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Bollobás, B, Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[2] Hedman, B, The maximum number of cliques in dense graphs, Discrete math., 54, 161-166, (1985) · Zbl 0569.05029
[3] Moon, J.W; Moser, L, On cliques in graphs, Israel J. math., 3, 23-28, (1965) · Zbl 0144.23205
[4] Roman, S, The maximum number of q-cliques in a graph with no p-clique, Discrete math., 14, 365-371, (1976) · Zbl 0319.05126
[5] Turan, P, On an extremal problem in graph theory, Mat. fiz. lapok, 48, 436-452, (1941)
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.