Another extremal problem for Turan graphs (Q1093651)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Another extremal problem for Turan graphs
scientific article

    Statements

    Another extremal problem for Turan graphs (English)
    0 references
    1987
    0 references
    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)\).
    0 references
    clique graph
    0 references
    clique number
    0 references
    Turan graph
    0 references
    multipartite graph
    0 references
    0 references
    0 references

    Identifiers