Property Pd,m and efficient design of reliable networks
Property Pd,m and efficient design of reliable networks
复制标题
属性 Pd,m 和可靠网络的高效设计
作者：
R. Faudree;R. Gould;Jeffrey S. Powell
Please try later.
For d ≥ 1 and m ≥ 1, a graph has property Pd,m if there exist at least m vertex‐disjoint paths of length at most d between each pair of vertices. Property Pd,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 Pd,m to other similar properties and then we prove several results regarding the extremal number for property Pd,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 = 4k + 2(k ≥ 1) and m ≥ 4. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012