Property P d , m and efficient design of reliable networks

For d ≥ 1 and m ≥ 1, a graph has property P d , m if there exist at least m vertex‐disjoint paths of length at most d between each pair of vertices. Property P d , m , which has a strong connection to wide diameter, is one way of measuring the reliability of a network. In this article, we first examine the relationship of P d , m to other similar properties and then we prove several results regarding the extremal number for property P d , m (the minimum number of edges needed for a graph to have the property). In particular, we find (i) the extremal number for graphs of certain orders when d = 2, (ii) several extremal graphs when d ≥ 3, (iii) a new lower bound on the extremal number when d ≥ 3, m ≥ 3, and (iv) a new upper bound on the extremal number when d , m are even with d = 4 k + 2( k ≥ 1) and m ≥ 4. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012