Classification and Enumeration of Minimum (d,1,3)-Graphs and Minimum (d,2,3)-Graphs.
Abstract
A (d,c,v)-graph is a c-connected graph of diameter =d in which each mode is of balence =v. The minimum order (number of nodes) of such graphs is denoted by micron (d,c,v), and a minimum (d,c,v)-graph is one of minimum order. Each minimum (d,c,v)-graph corresponds to an efficient way of arranging the stations of a communication network so that if any c-1 stations are incapacitated, the rest of the network is still connected, and so that in case of breakdown or other difficulty, each station can rely for assistance on precisely v others. The present paper classifies and counts the minimum (d,1,3)-graphs and the minimum (d,2,3)-graphs, a task performed elsewhere for the minimum (d,3,3)-graphs. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1976
- Accession Number
- ADA033613
Entities
People
- Howard Quaife
- Victor Klee
Organizations
- University of Washington