Another extremal problem for Turan graphs (Q1093651)

From MaRDI portal
Revision as of 09:50, 21 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
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