Technical Report CS0251

Title: Bounds on Path Connectivity
Authors: Alon Itai and Avram Zehavi
Abstract: The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound tor the path-connectivity of n^q (q < 1) separable graphs [LeiBO] is shown to exist.

If the edge connectivity of a graph is K(E) then between any two pairs of vertices and for every t<=K(E) there exists a t<=t'<=t+l such that there are t' paths between the first pair and K(E)-t between the second pair. All paths are edge-disjoint. Also if the edge-connecthity of a graph is >=4 then between any three pairs of vertices there are edge-disjoint paths.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1982
To the main CS technical reports page

Computer science department, Technion