Graph theory applied to optimal connectivity in computer networks

Abstract

This is a report on some of the research that has been carried out in applying graph theoretical results to communications networks. The networks that we wish to investigate here consist of computers at various sites which are linked together by telecommunications circuits. Many of the results of graph theory may be applied to such networks; we will restrict ourselves to the consideration of connectivity. In designing a computer communications network, it is desirable to provide good connectivity among all sites at reasonable cost. For this reason, extremes like the fully-connected network (too expensive) and the star network (only as reliable as its center) are usually not considered. The connectivity constraints or reliability measures can be stated in different ways, and analytic techniques have been developed for some of these measures. Further, procedures for the synthesis of well-connected networks have also been invented. The reliability of communications networks is an important issue in their design and operation. Telecommunications circuits become noisy and unusable, and the communications computers may also fail. This report is a survey of that part of applied graph theory which is useful in the study of the connectivity of communications networks.