Another extremal problem for Turan graphs
type: Item
instance of: scholarly article
title: Another extremal problem for Turan graphs
zbMATH Open document ID: 0629.05041
DOI: 10.1016/0012-365X(87)90139-7
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4023322
zbMATH Keywords: clique graph
zbMATH Keywords: clique number
zbMATH Keywords: Turan graph
zbMATH Keywords: multipartite graph
author: Bruce A. Hedman
reviewed by: S. F. Kapoor
MaRDI profile type: Publication
cites work: Q3852212
cites work: The maximum number of cliques in dense graphs
cites work: On cliques in graphs
cites work: The maximum number of q-cliques in a graph with no p-clique
cites work: Q5781249
full work available at URL: 0012-365x(87)90139-7
OpenAlex ID: W2016908703
description: scientific article; zbMATH DE number 4023322