A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs which require Δ+2colors. Apart from the above mentioned results, this thesis also contributes to the acyclic edge coloring literature by introducing new techniques like Recoloring, Color Exchange (exchanging colors of adjacent edges), circular shifting of colors on adjacent edges (derangement of colors). These techniques turn out to be very useful in proving upper bounds on the acyclic edge chromatic number.

This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.

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.