On Container Width and Length in Graphs, Groups,and Networks--Dedicated to Professor Paul Erdös on the occasion of his 80th birthday--

D.Frank HSU

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A    No.4    pp.668-680
Publication Date: 1994/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
distance,  diameter,  connectivity,  container,  

Full Text: PDF>>
Buy this Article

Graph parameters such as connectivity and diameter have been studied extensively due to their intrinsic importance in graph theory, combinatorics and their relations to (and applications in) fault tolerance and transmission delay in communications networks. The advent of VLSI technology and fiber optics material science has enabled us to design massively parallel processing computer systems and fast and complicated communications networks. All these systems increase their reliability by studying (among other) the existence of two (or more) disjoint paths connecting any two nodes. This paper addresses these issues by studying the width and length of containers in graphs and networks. In particular, the notions of w-distance and w-diameter on a graph are defined and studied which generalize both concepts of connectivity and diameter. Thses notions are also considered in finite groups. Other closely related parameters will be explored in the contexts of fault tolerance and routing. Known results are surveyed and open problems are offered for further investigation.