Diameter and Connectivity Considerations in the Design of Communication Networks
Abstract
A communication network is modeled by an undirected graph without loops and multiple edges. The maximal message delay index, in the network, is expressed in terms of the diameter of the graph. Three reliability measures are considered: a given minimal degree, edge-connectivity and vertex connectivity. Let H1(k,d) be the class of all graphs with diameter d and minimal degree k, H2(k,d) is a subclass of H2(k,d) consisting of all k-edge connected graphs in H1(k,d) and H3(k,d) is the subclass of all K-vertex connected graphs in H2(k,d). Hi(n,k,d) consists of the graphs in Hi(k,d) with exactly n vertices (i=1,2,3). Let fi(k,d), gi(k,d) be the minimum number of vertices and edges, respectively, that an Hi(k,d)- graph must have and let gi(n,k,d) be the minimal number of edges of an Hi(n,k,d)-graph (i=1,2,3). In Chapter 2 and 3 our main concern is to calculate the values of fi(k,d), gi(k,d) and gi(n,k,d) for arbitrary natural numbers n,k,d (i=1,2,3). Furthermore, graphs attaining the minimal number of vertices and edges are constructed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1976
- Accession Number
- ADA028367
Entities
People
- Jehuda Hartman
Organizations
- University of California, Los Angeles