A Chvátal-Erdős condition for (1,1)-factors in digraphs (Q1071779)

From MaRDI portal





scientific article; zbMATH DE number 3939386
Language Label Description Also known as
English
A Chvátal-Erdős condition for (1,1)-factors in digraphs
scientific article; zbMATH DE number 3939386

    Statements

    A Chvátal-Erdős condition for (1,1)-factors in digraphs (English)
    0 references
    0 references
    0 references
    1985
    0 references
    The authors prove: ''Let D be a k-connected digraph on at least two vertices such that \(k\geq \alpha (D)+p\). Then any set of vertex disjoint paths of D of total length at most p are contained in a (1,1)-factor of D.'' They conjecture: ''If D is a k-connected oriented graph on n vertices, with more than \((n(n-1)-k(k+1))/2\) arcs, then D is hamiltonian.''
    0 references
    circuit
    0 references
    hamiltonian digraph
    0 references
    independence number
    0 references
    vertex disjoint paths
    0 references
    factor
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references