On line disjoint paths of bounded length

✍ Scribed by Geoffrey Exoo

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 105 KB
• Volume: 44
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90197-8

✦ Synopsis

In a recent paper Lovfisz, Neumann-Lara and Plummer proved some Mengerian theorems for paths of bounded length. In this note the line connectivity analogue of their problem "is considered.

In [3] Lovfisz, Neumann-Lara and Plummer considered the problem of extending Monger's theorem to paths of bounded length. Given a graph G and nonadjacent points x and y of G they defined Sk(x, y; G) to be the minimum number of points whose removal increases the distance from x to y to more than k, and defined Ik(x, y; G) to be the maximum number of internally disjoilJt x-y paths whose length does not exceed k. They focused their study on the ratio Sk(x, y; G)/l~(x, y; G) and in particular on how large this ratio can be. If fo(k) is defined to be the supremum of the ratio taken over all graphs G and all nonadjacent points x and y, then they showed that fo(k)~ [~k].

In [2] it was shown that fo(k)>~[¼(k +3)], settling a conjecture of Lovfisz [1, p. 248] that fo(k)~x/-k. (The lower bound has recently been improved to [](k + 1)]