Master of Science / Department of Computing and Information Sciences / William H. Hsu / This thesis discusses the background and methodologies necessary for constructing features in order to discover hidden links in relational data. Specifically, we consider the problems of predicting, classifying and annotating friends relations in friends networks, based upon features constructed from network structure and user profile data. I first document a data model for the blog service LiveJournal, and define a set of machine learning problems such as predicting existing links and estimating inter-pair distance. Next, I explain how the problem of classifying a user pair in a social networks, as directly connected or not, poses the problem of selecting and constructing relevant features. In order to construct these features, a genetic programming approach is used to construct multiple symbol trees with base features as their leaves; in this manner, the genetic program selects and constructs features that many not have been considered, but possess better predictive properties than the base features. In order to extract certain graph features from the relatively large social network, a new shortest path search algorithm is presented which computes and operates on a Euclidean embedding of the network. Finally, I present classification results and discuss the properties of the frequently constructed features in order to gain insight on hidden relations that exists in this domain.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

The queens graph Qn has the squares of then x n chessboard as its vertices; two squares are adjacent if they are in the same row, column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote the minimum size of an independent dominating set of Qn. The main purpose of this thesis is to determine new values for'!'( Qn). We begin by discussing the most important known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known values of 'J'(Qn) and explain how they were determined. We briefly explain how to obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It is often useful to study these small dominating sets to look for patterns and possible generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 ) and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3, thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper bound')' (Qn) :s; 1 8 5n + 0 (1), which is better than known bounds in the literature and in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8 we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)

Thesis (MSc.)--University of Stellenbosch, 2000. / ENGLISH ABSTRACT: The notion of a classical graph theoretic Ramsey number is generalized by assuming that both the original graph whose edges are arbitrarily bicoloured and the monochromatic subgraphs to be forced are complete, balanced, multipartite graphs, instead of complete graphs as in the standard definition. Some small multipartite Ramsey numbers are found, while upper- and lower bounds are established for others. Analytic arguments as well as computer searches are used. / AFRIKAANSE OPSOMMING: Die klassieke grafiek-teoretiese definisie van ’n Ramsey getal word veralgemeen deur te aanvaar dat beide die oorspronklike grafiek, waarvan die lyne willekeurig met twee kleure gekleur word en die gesogte subgrafieke almal volledige, gebalanseerde, veelledige grafieke is, anders as in die standaard definisie. Klein veelledige Ramsey getalle word gevind, terwyl bo- en ondergrense vir ander daargestel word. Analitiese argumente en rekenaarsoektogte word gebruik.

Thesis (MSc)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: The main objective of our study is enumerating spanning trees (G) and perfect matchings PM(G) on graphs G and lattices L. We demonstrate two methods of enumerating spanning trees of any connected graph, namely the matrix-tree theorem and as a special value of the Tutte polynomial T(G; x; y). We present a general method for counting spanning trees on lattices in d 2 dimensions. In particular we apply this method on the following regular lattices with d = 2: rectangular, triangular, honeycomb, kagomé, diced, 9 3 lattice and its dual lattice to derive a explicit formulas for the number of spanning trees of these lattices of finite sizes. Regarding the problem of enumerating of perfect matchings, we prove Cayley’s theorem which relates the Pfaffian of a skew symmetric matrix to its determinant. Using this and defining the Pfaffian orientation on a planar graph, we derive explicit formula for the number of perfect matchings on the following planar lattices; rectangular, honeycomb and triangular. For each of these lattices, we also determine the bulk limit or thermodynamic limit, which is a natural measure of the rate of growth of the number of spanning trees (L) and the number of perfect matchings PM(L). An algorithm is implemented in the computer algebra system SAGE to count the number of spanning trees as well as the number of perfect matchings of the lattices studied. / AFRIKAANSE OPSOMMING: Die hoofdoel van ons studie is die aftelling van spanbome (G) en volkome afparings PM(G) in grafieke G en roosters L. Ons beskou twee metodes om spanbome in ’n samehangende grafiek af te tel, naamlik deur middel van die matriks-boom-stelling, en as ’n spesiale waarde van die Tutte polinoom T(G; x; y). Ons behandel ’n algemene metode om spanbome in roosters in d 2 dimensies af te tel. In die besonder pas ons hierdie metode toe op die volgende reguliere roosters met d = 2: reghoekig, driehoekig, heuningkoek, kagomé, blokkies, 9 3 rooster en sy duale rooster. Ons bepaal eksplisiete formules vir die aantal spanbome in hierdie roosters van eindige grootte. Wat die aftelling van volkome afparings aanbetref, gee ons ’n bewys van Cayley se stelling wat die Pfaffiaan van ’n skeefsimmetriese matriks met sy determinant verbind. Met behulp van hierdie stelling en Pfaffiaanse oriënterings van planare grafieke bepaal ons eksplisiete formules vir die aantal volkome afparings in die volgende planare roosters: reghoekig, driehoekig, heuningkoek. Vir elk van hierdie roosters word ook die “grootmaat limiet” (of termodinamiese limiet) bepaal, wat ’n natuurlike maat vir die groeitempo van die aantaal spanbome (L) en die aantal volkome afparings PM(L) voorstel. ’n Algoritme is in die rekenaaralgebra-stelsel SAGE geimplementeer om die aantal spanboome asook die aantal volkome afparings in die toepaslike roosters af te tel.

The network design is a planning process of placing system components to provide service or meet certain needs in an economical way. It has strong links to real application areas, such as transportation network, communication network, supply chain, power grid, water distribution systems, etc. In practice, these infrastructures are very vulnerable to any failures of system components. Therefore, the design of such infrastructure networks should be robust and survivable to any failures caused by many factors, for example, natural disasters, intentional attacks, system limits, etc. In this dissertation, we first summarize the background and motivations of our research topic on network design problems. Different from literature on network design, we consider both uncertain node and link failures during the network design process. The first part of our research is to design a survivable network with mixed connectivity requirements, or the (k,l)-connectivity. The designed network can still be connected after failures of any k vertices and (l-1) edges or failures of any (k-1) vertices and l edges. After formally proving its relationships to edge and vertex disjoint paths, we present two integer programming (IP) formulations, valid inequalities to strengthen the IP formulations, and a cutting plane algorithm. Numerical experiments are performed on randomly generated graphs to compare these approaches. Special cases of this problem include: when k=0, l=1, this problem becomes the well-known minimum spanning tree problem; and when k=0, l ≥ 1, this problem is to find a minimum-cost l-edge-connected spanning subgraph, while when k ≥ 2, l=0, the problem is to find a minimum-cost k-vertex-connected spanning subgraph. As a generalization of k-minimum spanning tree and λ-edge-connected spanning subgraph problems for network design, we consider the minimum-cost λ-edge-connected k-subgraph problem, or the (k, λ)-subgraph problem, which is to find a minimum-cost λ-edge-connected subgraph of a graph with at least k vertices. This problem can be considered as designing k-minimum spanning tree with higher connectivity requirements. We also propose several IP formulations for exactly solving the (k, λ)-subgraph problem, based on some graph properties, for example, requirements of cutsets for a division of the graph and paths between any two vertices. In addition, we study the properties of (k,2)-subgraphs, such as connectivity, bridgeless, and strong orientation properties. Based on these properties, we propose several stronger and more compact IP formulations for solving the (k,2)-subgraph problem, which is a direct generalization of the k-minimum spanning tree problem. Serving as a virtual backbone for wireless ad hoc networks, the connected dominating set problem has been widely studied. We design a robust and survivable connected dominating set for a virtual backbone of a larger graph for ad hoc network. More specifically, we study the (k,l)-connected d-dominating set problem. Given a graph G=(V,E), a subset D ⊆ V is a (k,l)-connected d-dominating set if the subgraph induced by D has mixed connectivity at least (k,l) and every vertex outside of S has at least d neighbors from D. The type of virtual backbone is survivable and also robust for sending message under certain number of both node and link failures. We study the properties of such dominating set and also IP formulations. In addition, we design a cutting plane algorithm to solve it.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple greedy algorithm that assigns the highest degree to the root, the second, the third, . . . , -highest degree to the root’s neighbours, etc. This particular tree is the solution to numerous extremal problems among all trees with given degree sequence. In this thesis, we collect results for some distancebased graph invariants, the number of subtrees and the spectral radius in which greedy trees play a major role. We show that greedy trees are extremal for the aforementioned graph invariants by means of two different approaches, one using level greedy trees and majorization, while the other one is somewhat more direct. Finally, we prove some new results on greedy trees for additive parameters with specific toll functions. / AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige gulsige algoritme gebou, wat die hoogste graad aan die wortel toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure, ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale probleme onder al die bome met gegewe graadry. In hierdie tesis beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante, die aantal subbome en die spektraalstraal waarin gulsige bome ’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik te maak: een met behulp van vlak-gulsige bome en majorering, en ’n ander metode wat effens meer direk is. Laastens bewys ons sommige nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke tolfunksies.

Thesis (MComm) -- Stellenbosch University, 2002. / ENGLISH ABSTRACT: Consider a data set with a categorical response variable and a set of explanatory variables. The response variable can have two or more categories and the explanatory variables can be numerical or categorical. This is a typical setup for a classification analysis, where we want to model the response based on the explanatory variables. Traditional statistical methods have been developed under certain assumptions such as: the explanatory variables are numeric only and! or the data follow a multivariate normal distribution. hl practice such assumptions are not always met. Different research fields generate data that have a mixed structure (categorical and numeric) and researchers are often interested using all these data in the analysis. hl recent years robust methods such as classification trees have become the substitute for traditional statistical methods when the above assumptions are violated. Classification trees are not only an effective classification method, but offer many other advantages. The aim of this thesis is to highlight the advantages of classification trees. hl the chapters that follow, the theory of and further developments on classification trees are discussed. This forms the foundation for the CART software which is discussed in Chapter 5, as well as other software in which classification tree modeling is possible. We will compare classification trees to parametric-, kernel- and k-nearest-neighbour discriminant analyses. A neural network is also compared to classification trees and finally we draw some conclusions on classification trees and its comparisons with other methods. / AFRIKAANSE OPSOMMING: Beskou 'n datastel met 'n kategoriese respons veranderlike en 'n stel verklarende veranderlikes. Die respons veranderlike kan twee of meer kategorieë hê en die verklarende veranderlikes kan numeries of kategories wees. Hierdie is 'n tipiese opset vir 'n klassifikasie analise, waar ons die respons wil modelleer deur gebruik te maak van die verklarende veranderlikes. Tradisionele statistiese metodes is ontwikkelonder sekere aannames soos: die verklarende veranderlikes is slegs numeries en! of dat die data 'n meerveranderlike normaal verdeling het. In die praktyk word daar nie altyd voldoen aan hierdie aannames nie. Verskillende navorsingsvelde genereer data wat 'n gemengde struktuur het (kategories en numeries) en navorsers wil soms al hierdie data gebruik in die analise. In die afgelope jare het robuuste metodes soos klassifikasie bome die alternatief geword vir tradisionele statistiese metodes as daar nie aan bogenoemde aannames voldoen word nie. Klassifikasie bome is nie net 'n effektiewe klassifikasie metode nie, maar bied baie meer voordele. Die doel van hierdie werkstuk is om die voordele van klassifikasie bome uit te wys. In die hoofstukke wat volg word die teorie en verdere ontwikkelinge van klassifikasie bome bespreek. Hierdie vorm die fondament vir die CART sagteware wat bespreek word in Hoofstuk 5, asook ander sagteware waarin klassifikasie boom modelering moontlik is. Ons sal klassifikasie bome vergelyk met parametriese-, "kernel"- en "k-nearest-neighbour" diskriminant analise. 'n Neurale netwerk word ook vergelyk met klassifikasie bome en ten slote word daar gevolgtrekkings gemaak oor klassifikasie bome en hoe dit vergelyk met ander metodes.

It is known that graph theoretic models have extensive application to real-life discrete optimization problems. Many of these models are NP-hard and, as a result, exact methods may be impractical for large scale problem instances. Consequently, there is a great interest in developing e±cient approximate methods that yield near-optimal solutions in acceptable computational times. A class of such methods, known as metaheuristics, have been proposed with success. This thesis considers some recently proposed NP-hard combinatorial optimization problems formulated on graphs. In particular, the min- imum labelling spanning tree problem, the minimum labelling Steiner tree problem, and the minimum quartet tree cost problem, are inves- tigated. Several metaheuristics are proposed for each problem, from classical approximation algorithms to novel approaches. A compre- hensive computational investigation in which the proposed methods are compared with other algorithms recommended in the literature is reported. The results show that the proposed metaheuristics outper- form the algorithms recommended in the literature, obtaining optimal or near-optimal solutions in short computational running times. In addition, a thorough analysis of the implementation of these methods provide insights for the implementation of metaheuristic strategies for other graph theoretic problems.

Thesis (PhD (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2004. / Suppose a lottery scheme consists of randomly selecting an unordered winning n-subset from a universal set of m numbers, while a player participates in the scheme by purchasing a playing set of any number of unordered n-subsets from the same universal set prior to a winning draw, and is awarded a prize if ...