Premium
Property P d , m and efficient design of reliable networks
Author(s) -
Faudree Ralph J.,
Gould Ronald J.,
Powell Jeffrey S.
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21456
Subject(s) - combinatorics , mathematics , upper and lower bounds , disjoint sets , connection (principal bundle) , graph , vertex (graph theory) , property (philosophy) , discrete mathematics , geometry , epistemology , mathematical analysis , philosophy
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