No description available.

No description available.

No description available.

No description available.

Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.

Shifting attention from the plane to the sphere and torus, we extend the study of pseudo-triangulations. Planar representations of each surface are used. A number of theorems and concepts are taken from the plane and applied to the sphere and torus not only for pseudo-triangulations but for triangulations as well. We found the number of edges and faces in a triangulation on n vertices in the plane, on the sphere and on the torus.

An efficient air transport system is an important part of social and economic development of Southern African Development Community (SADC). Efficient intra-SADC air service connections enhance regional integration, access to the global economy, international tourism and contribute towards the vision to establish the African Economic Community by 2034. SADC, in July 1998, embarked on liberalisation of the regional civil aviation sector in order to enhance the efficiency of air transport services. In the United States of America and European Union, the liberalisation of air transport has transformed civil aviation networks. The fragmentation of air service connections on the intra-SADC network in the midst of the liberalisation process is symptomatic of a poor implementation strategy coupled with air transport market imperfections. The purpose of this thesis is to examine, understand and explain the factors that influence the disintegration of the intra-SADC air transport network .The aim is to identify how regional air transport services can be transformed to meet the social and economic demands of the region. This research adopts network theory, as the conceptual framework of the investigation. Assuming a graph approaching maximal connection as the sought after state of affairs for SADC; this study benchmarked the post liberalisation network structure to the regional economic communities of ASEAN and MERCOSUR. The aim of the benchmarking is to identify the extend of the differences in air transport network in those two regions, resulting from the policies adopted and to establish how the SADC policies may be improved and implemented more efficiently. The findings of the study are that, in comparison to the two developing regions, SADC’s liberalisation measures have failed. The study developed and evaluated an econometric model which analysed demand patterns on the intra-SADC passenger air transport network. Although low levels of passenger demand seem to characterise the majority of SADC city-pairs, the study identified nodes with sufficient demand to justify direct connections which would in turn reduce network fragmentation. This research also establishes that the absence of a realistic detailed roadmap, an ill-defined programme of action and inadequate resources contributed to the failure of SADC’s liberalisation strategy. In its final sections, this study proposes an ideal demand-driven network configuration and offers specific recommendations to SADC member states for that network to be functional. The proposed network improves network connectivity from the current poor levels, where a connectivity measure of 15% suggests underdevelopment, to levels over 40%. The study however, acknowledges that air transport liberalisation does not necessarily guarantee equitable distribution of network efficiency in developing regions. There are communities that cannot sustain commercially viable air service connections without economic subvention, probably in the form of the Public Service Obligation (PSO) programme adopted in the EU.

An efficient air transport system is an important part of social and economic development of Southern African Development Community (SADC). Efficient intra-SADC air service connections enhance regional integration, access to the global economy, international tourism and contribute towards the vision to establish the African Economic Community by 2034. SADC, in July 1998, embarked on liberalisation of the regional civil aviation sector in order to enhance the efficiency of air transport services. In the United States of America and European Union, the liberalisation of air transport has transformed civil aviation networks. The fragmentation of air service connections on the intra-SADC network in the midst of the liberalisation process is symptomatic of a poor implementation strategy coupled with air transport market imperfections. The purpose of this thesis is to examine, understand and explain the factors that influence the disintegration of the intra-SADC air transport network .The aim is to identify how regional air transport services can be transformed to meet the social and economic demands of the region. This research adopts network theory, as the conceptual framework of the investigation. Assuming a graph approaching maximal connection as the sought after state of affairs for SADC; this study benchmarked the post liberalisation network structure to the regional economic communities of ASEAN and MERCOSUR. The aim of the benchmarking is to identify the extend of the differences in air transport network in those two regions, resulting from the policies adopted and to establish how the SADC policies may be improved and implemented more efficiently. The findings of the study are that, in comparison to the two developing regions, SADC’s liberalisation measures have failed. The study developed and evaluated an econometric model which analysed demand patterns on the intra-SADC passenger air transport network. Although low levels of passenger demand seem to characterise the majority of SADC city-pairs, the study identified nodes with sufficient demand to justify direct connections which would in turn reduce network fragmentation. This research also establishes that the absence of a realistic detailed roadmap, an ill-defined programme of action and inadequate resources contributed to the failure of SADC’s liberalisation strategy. In its final sections, this study proposes an ideal demand-driven network configuration and offers specific recommendations to SADC member states for that network to be functional. The proposed network improves network connectivity from the current poor levels, where a connectivity measure of 15% suggests underdevelopment, to levels over 40%. The study however, acknowledges that air transport liberalisation does not necessarily guarantee equitable distribution of network efficiency in developing regions. There are communities that cannot sustain commercially viable air service connections without economic subvention, probably in the form of the Public Service Obligation (PSO) programme adopted in the EU.

Extremal Functions for Graph Linkages and Rooted Minors Paul Wollan 137 pages Directed by: Robin Thomas A graph G is k-linked if for any 2k distinct vertices s_1,..., s_k,t_1,..., t_k there exist k vertex disjoint paths P_1,...,P_k such that the endpoints of P_i are s_i and t_i. Determining the existence of graph linkages is a classic problem in graph theory with numerous applications. In this thesis, we examine sufficient conditions that guarantee a graph to be k-linked and give the following theorems. (A) Every 2k-connected graph on n vertices with 5kn edges is k-linked. (B) Every 6-connected graph on n vertices with 5n-14 edges is 3-linked. The proof method for Theorem (A) can also be used to give an elementary proof of the weaker bound that 8kn edges suffice. Theorem (A) improves upon the previously best known bound due to Bollobas and Thomason stating that 11kn edges suffice. The edge bound in Theorem (B) is optimal in that there exist 6-connected graphs on n vertices with 5n-15 edges that are not 3-linked. The methods used prove Theorems (A) and (B) extend to a more general structure than graph linkages called rooted minors. We generalize the proof methods for Theorems (A) and (B) to find edge bounds for general rooted minors, as well as finding the optimal edge bound for a specific family of bipartite rooted minors. We conclude with two graph theoretical applications of graph linkages. The first is to the problem of determining when a small number of vertices can be used to cover all the odd cycles in a graph. The second is a simpler proof of a result of Boehme, Maharry and Mohar on complete minors in huge graphs of bounded tree-width.

We study codes that have identifiable parent property. Such codes are called IPP codes. Research on IPP codes is motivated by design of schemes that protect against piracy of digital products. Construction and decoding of maximum IPP codes have been studied in rich literature. General bounds on F(n,q), the maximum size of IPP codes of length n over an alphabet with q elements, have been obtained through the use of techniques from graph theory and combinatorial design. Improved bounds on F(3,q) and F(4,q) are obtained. Probabilistic techniques are also used to prove the existence of certain IPP codes. We prove a precise formula for F(3,q), construct maximum IPP codes with size F(3,q), and give an efficient decoding algorithm for such codes. The main techniques used in this thesis are from graph theory and nonlinear optimization. Our approach may be used to improve bounds on F(2k+1, q). For example, we characterize the associated graphs of maximum IPP codes of length 5, and obtain bounds on F(5,q).