A note concerning paths and independence number in digraphs (Q913811)

From MaRDI portal





scientific article; zbMATH DE number 4148114
Language Label Description Also known as
English
A note concerning paths and independence number in digraphs
scientific article; zbMATH DE number 4148114

    Statements

    A note concerning paths and independence number in digraphs (English)
    0 references
    0 references
    0 references
    1990
    0 references
    The authors show that there exist digraphs D such that for all paths \(P_ 1\) and \(P_ 2\) we \(\alpha (D\setminus (P_ 1\cup P_ 2))=\alpha (D)\) They believe that \(f(k)=k(f(k))\) is the smallest integer such that if D is any digraph with \(\alpha (D)=k\) then D contains f(k) paths \(P_ i\) such that \(\alpha (D\setminus \cup_{i=1}^{f(k)}P_ i)<\alpha (D))\).
    0 references
    path covering
    0 references
    independence number
    0 references
    digraphs
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references