Connectivity and Superconnectivity of digraphs with prescribed semigirth

JianMin Tang

Abstract

Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph or a digraph. In this talk, we focus on digraphs. Fault tolerance is an important performance feature when designing a network, and the connectivity and superconnectivity of the digraphs are important measures of fault tolerance for a network. To study these measurements a parameter related to the number of shortest paths was introduced by J.Fabrega and M.A.Fiol in 1989, which recently has received the name of semigirth from the Handbook of Graph Theory in 2003. To obtain results on connectivity and superconnectivity of digraphs with given semigirth, first lower bounds of connectivity and superconnectivity in digraphs in terms of semigirth are obtained. Then to improve the above results, a