Extremal networks and connectivity

In this thesis we consider questions in two separate but related research areas in the field of graph theory, namely, extremal graph theory and connectivity. Extremal graph theory is the study of graphs that are extremal, that is, maximal or minimal, under some given constraints. In this thesis we focus on the problem of finding the maximum number of pair-wise connections between the nodes in a network, given the number of nodes and the length of the shortest cycle in the network. A graph that attains this bound is called an extremal graph. Our interest in extremal graphs arose from the problem of determining the structure of the most efficient and reliable networks. We provide constructions that produce infinite families of extremal graphs. We examine the relationship between extremal graphs and some other graphs that have been considered in the design of optimal networks. We develop an algorithm that we use to establish new and improved lower bounds on the size of some extremal graphs and determine the exact size of the extremal graphs for some particular parameters. A graph is connected if there is a path, consisting of nodes and links, between any two nodes in the graph. The ability to send and receive email via the Internet is dependent upon the Internet being connected, that is, there is a path of computers and connections between the sender and receiver of the email. The connectivity of a network is the number of nodes or links that must be removed in order to partition the network into two or more components. High connectivity of a network corresponds to the properties of fault tolerance and resilience under attack. In this thesis we determine a number of sufficient conditions that ensure good connectivity of a network.