Property Pd,m and efficient design of reliable networks

✍ Scribed by Ralph J. Faudree; Ronald J. Gould; Jeffrey S. Powell

• Publisher: John Wiley and Sons
• Year: 2012
• Tongue: English
• Weight: 199 KB
• Volume: 60
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.21456

✦ Synopsis

Abstract

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