Different capacities of a digraph (Q1334937)

From MaRDI portal
Revision as of 17:04, 22 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Different capacities of a digraph
scientific article

    Statements

    Different capacities of a digraph (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    26 September 1994
    0 references
    The \(n\)-th Sperner power \(G^ n\) of a digraph \(G\) with vertex set \(V\) has vertex set \(V^ n\) and contains edges \((x_ 1x_ 2 \cdots x_ n, y_ 1y_ 2 \cdots y_ n)\) if and only if \(G\) contains edge \((x_ i, y_ i)\) for at least one \(i\), \(1 \leq i \leq n\). If \(C\) is a class of digraphs closed under Sperner products, let \(F(G^ n)\) denote the cardinality of the largest subgraph from \(C\) contained as an induced subgraph of \(G^ n\); then \(\lim_{n \to \infty}n^{ - 1} \cdot \log F (G^ n)\) may be called the \(C\)-capacity of \(G\). The authors derive upper and lower bounds for various capacity functions and investigate the conditions under which they are tight.
    0 references
    clique number
    0 references
    chromatic number
    0 references
    independence graphs
    0 references
    Sperner power
    0 references
    digraph
    0 references
    Sperner products
    0 references
    capacity
    0 references
    0 references

    Identifiers