Bounds on path connectivity (Q761468)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bounds on path connectivity
scientific article

    Statements

    Bounds on path connectivity (English)
    0 references
    0 references
    0 references
    1984
    0 references
    A graph is k-path-connected if it has at least 2k vertices and, for any k pairs of distinct vertices, there are k disjoint paths connecting them. The authors prove a result implying the existence of a function f(d) such that no planar graph of maximum degree d is f(d)-path-connected. For edge-connectivity the following interpolation theorem is proved: Let \(s_ 1,t_ 1,s_ 2,t_ 2\) be vertices such that, for each \(i=1,2\), there are k edge-disjoint paths between \(s_ i\) and \(t_ i\) and let m be any natural number less than k. Then the graph contains a collection of m edge-disjoint paths such that m or \(m+1\) of these connect \(s_ 1\) and \(t_ 1\) and the others connect \(s_ 2\) and \(t_ 2\).
    0 references
    path-connected graphs
    0 references

    Identifiers