Variations of classical extremal graph theoretical problems: Moore bound and connectivity

Interconnection networks form an important research area which has received much attention, both in theoretical research and in practice. Design of interconnection networks is much concerned with the topology of networks. The topology of a network is usually studied in terms of extremal graph theory. Consequently, from the extremal graph theory point of view, designing the topology of a network involves various extremal graph problems. One of these problems is the well-known fundamental problem called the degree/diameter problem, which is to determine the largest (in terms of the number of vertices) graphs or digraphs of given maximum degree and given diameter. General upper bounds, called Moore bounds, exist for the largest possible order of such graphs and digraphs of given maximum degree ∆ (respectively, out-degree d) and diameter D. However, quite a number of open problems regarding the degree/diameter problem do still exist. Some of these problems, such as constructing a Moore graph of degree ∆ = 57 and diameter D = 2, have been open for over 50 years. Another extremal graph problem regarding the design of the topology of a network is called the construction of EX graphs, which is to obtain graphs of the largest size (in terms of the number of edges), given order and forbidden cycle lengths. In this thesis, we obtain large graphs whose sizes either improve the lower bound of the size of EX graphs, or even reach the optimal value. We deal with designing the topology of a network, but we are also interested in the issue of fault tolerance of interconnection networks. This leads us to another extremal graph problem, that is, connectivity. In this thesis, we provide an overview of the current state of research in connectivity of graphs and digraphs. We also present our contributions to the connectivity of general regular graphs with small diameter, and the connectivity of EX graphs.