Thesis (Ph.D.) - University of St Andrews, June 2010.

Thesis (M. Phil.)--University of Hong Kong, 1999.

Ph.D. / In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis. In Chapter 2 we establish a lower bound for the minus k-subdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks-101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks-101 is NP-complete, even for bipartite graphs. In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks-11 for comets and cycles. In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NP-complete. Chapter 5 features the minus bondage number b- (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b- is given for trees. Finally, we show that the decision problem corresponding to the computation of b- is N P - hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.

M.Sc. / Let G be a graph and D a set of vertices such that every vertex in G is in D or adjacent to at least one vertex in D. Then D is called a dominating set of G and the smallest cardinality of such a dominating set of G is known as the domination number of G, denoted by y(G). This short dissertation is a study of the domination number in graphs with bounds on both the minimum and maximum degrees. In Chapter 1 we give all definitions, terminology and references related to the material presented in this thesis. In Chapter 2 we study an article by McCuaig and Shepherd which considers graphs with minimum degree two and gives an upper bound for their domination numbers in terms of their order. This bound is also an improvement of one originally determined by Ore. In Chapter 3 an article by Fisher, Fraughnaugh and Seager is studied. Here the domination number in graphs with maximum degree at most three is discussed. Furthermore au upper bound on the domination number of a graph is given in terms of its order, size and the number of isolated vertices it contains. This result is an extension of a previous result by Reed on domination in graphs with minimum degree three. A set U of vertices of a graph G = (V, E) is k-dominating if each vertex of V — U is adjacent to at least k vertices of U. The k-domination number of G, Yk (G), is the smallest cardinality of a k-dominating set of G. Finally in Chapter 4 we study an article by Cockayne, Gamble and Shepherd which gives an upper bound for the k-domination number of a graph with minimum degree at least k. This result is a generalization of a result by Ore.

During the last decade, there have been major advances in solving a class of large-scale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems. This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems. For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are series-parallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case. For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the ATSP case, we develop a Tree Composition method, which generates all non-spanning clique tree facetial inequalities. / Business, Sauder School of / Graduate

"This paper is concerned with systems of distinct representatives (abbreviated by S.D.R.) and related combinatorial topics"--Introduction. / Typescript. / "August, 1959." / "Submitted to the Graduate Council of Florida State University in partial fulfillment of the requirements for the degree of Master of Science." / Advisor: Marion F. Tinsley, Professor Directing Paper. / Includes bibliographical references (leaf 25).

Gives the basic definitions and theorems of similar partially ordered sets; studies finite partially ordered sets, including the problem of combinatorial analysis; and includes the ideas of complete, dense, and continuous partially ordered sets, including proofs.

Thesis (Ph.D.)--University of the Witwatersrand, Faculty of Science, 1998. / A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Doctor of Philosophy. Johannesburg 1998 / Let A = (aij) be an m x n matrix. There is a natural way to associate a poset PA with A. A jump in a linear extension of PA is a pair of consecutive elements which are incomparable in Pa. The jump number of A is the minimum number of jumps in any linear extension of PA. The maximum jump number over a class of n x n matrices of zeros and ones with constant row and column sum k, M (n, k), has been investigated in Chapter 2 and 3. Chapter 2 deals with extremization problems concerning M (n ,k). In Chapter 3, we obtain the exact values for M (11,k). M(n,Q), M (n,n-3) and M(n,n-4). The concept of frequency hyperrectangle generalizes the concept of latin square. In Chapter 4 we derive a bound for the maximum number of mutually orthogonal frequency hyperrectangles. Chapter 5 gives two algorithms to construct mutually orthogonal frequency hyperrectangles. Chapter 6 is devoted to some enumerative results about Carlitz compositions (compositions with different adjacent parts).

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2017. / In this thesis, various partition functions with respect to `-regular overpartitions, a special partition inequality and partition con gurations are studied. We explore new combinatorial properties of overpartitions which are natural generalizations of integer partitions. Building on recent work, we state general combinatorial identities between standard partition, overpartition and `-regular partition functions. We provide both generating function and bijective proofs. We then establish an in nite set of Ramanujan-type congruences for the `-regular overpartitions. This signi cantly extends the recent work of Shen which focused solely on 3{regular overpartitions and 4{regular overpartitions. We also prove some of the congruences for `-regular overpartition functions combinatorially. We then provide a combinatorial proof of the inequality p(a)p(b) > p(a+b), where p(n) is the partition function and a; b are positive integers satisfying a+b > 9, a > 1 and b > 1. This problem was posed by Bessenrodt and Ono who used the inequality to study a maximal multiplicative property of an extended partition function. Finally, we consider partition con gurations introduced recently by Andrews and Deutsch in connection with the Stanley-Elder theorems. Using a variation of Stanley's original technique, we give a combinatorial proof of the equality of the number of times an integer k appears in all partitions and the number of partition con- gurations of length k. Then we establish new generalizations of the Elder and con guration theorems. We also consider a related result asserting the equality of the number of 2k's in partitions and the number of unrepeated multiples of k, providing a new proof and a generalization. / MT2017

The mathematical theory of nding a basis of shortest possible vectors in a given lattice L is known as reduction theory and goes back to the work of Lagrange, Gauss, Hermite, Korkin, Zolotarev, and Minkowski. Modern reduction theory is voluminous and includes the work of A. Lenstra, H. Lenstra and L. Lovasz who created the well known LLL algorithm, and many other researchers such as L. Babai and C. P. Schnorr who created signi cant new variants of basis reduction algorithms. The shortest vector (SVP) and closest vector (CVP) problems, presently considered intractable, are algorithmic tasks that lie at the core of many number theoretic problems, integer programming, nding irreducible factors of polynomials, minimal polynomials of algebraic numbers, and simultaneous diophantine approximation. Lattice basis reduction also has deep and extensive connections with modern cryptography, and cryptanalysis particularly in the post-quantum era. In this dissertation we study and compare current systems LLL and BKZ, and point out their strengths and drawbacks. In addition, we propose and investigate the e cacy of new optimization techniques, to be used along with LLL, such as hill climbing, random walks in groups, our lattice di usion-sub lattice fusion, and multistage hybrid LDSF-HC technique. The rst two methods rely on the sensitivity of LLL to permutations of the input basis B, and optimization ideas over the symmetric group Sm viewed as a metric space. The third technique relies on partitioning the lattice into sublattices, performing basis reduction in the partition sublattice blocks, fusing the sublattices, and repeating. We also point out places where parallel computation can reduce runtimes achieving almost linear speedup. The multistage hybrid technique relies on the lattice di usion and sublattice fusion and hill climbing algorithms. Unlike traditional methods, our approach brings in better results in terms of basis reduction towards nding shortest vectors and minimal weight bases. Using these techniques we have published the competitive lattice vectors of ideal lattice challenge on the lattice hall of fame. Toward the end of the dissertation we also discuss applications to the multidimensional knapsack problem that resulted in the discovery of new large sets of geometric designs still considered very rare. The research introduces innovative techniques in lattice basis reduction theory and provides some space for future researchers to contemplate lattices from a new viewpoint. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2016. / FAU Electronic Theses and Dissertations Collection