# 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

##### MSC:
 05C35 Extremal problems in graph theory
##### Keywords:
clique graph; clique number; Turan graph; multipartite graph
Full Text:
##### References:
  Bollobás, B, Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031  Hedman, B, The maximum number of cliques in dense graphs, Discrete math., 54, 161-166, (1985) · Zbl 0569.05029  Moon, J.W; Moser, L, On cliques in graphs, Israel J. math., 3, 23-28, (1965) · Zbl 0144.23205  Roman, S, The maximum number of q-cliques in a graph with no p-clique, Discrete math., 14, 365-371, (1976) · Zbl 0319.05126  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.