Structural Properties of Some Interconnection Networks

Abstract

Interconnection networks are usually regular graphs so we will restrict our scope of this talk to regular graphs.Connectivity is a basic measure of vulnerability of a network. Many generalizations or advanced alternatives have been proposed such as restricted connectivity and toughness. In this talk, we will consider an example of this. Suppose an r-regular graph has connectivity r and deleting vertices of an optimal disconnecting set results in a graph with two components, one of which is a singleton. Then in a sense, the ``core'' of the graph is still intact. There are several terms to describe such a graph, one of which is tightly super connnected. In this talk, we consider a generalization of this. An r-regular graph is super m-connected of order q if with at most m vertices deleted, the resulting graph is either connected or it has one big component and a number of small components with at most q vertices in total. (Similarly for m-edge-connected of order q.) We study this measure for a number of interconnection networks such as the star graphs, the alternating group graphs and their generalizations. In addition, we will also consider several implications of these results. Joint work with many, most notably, László Lipták.

Thursday, October 28, 2010

2:30 – 3:30 P.M.

372 Science and Engineering Building

(Refreshments at 2:00-2:30 PM in the kitchen area adjacent to 368 SEB)