Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree. 5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity 6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering. 7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ log log Δ factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.

A partial matrix, is a matrix for which some entries are specified and some unspecified. In general completion problems ask whether a given partial matrix, may be completed to a matrix where all the entries are specified, such that this completion admits a specific structure. The positive definite completion problem asks whether a partial Hermitian matrix admits a completion such that the completed matrix is positive semidefinite. The minimum solution criterion, is that every fully specified principal submatrix is nonnegative. Then the set of partial Hermitian matrices, which admit a positive semidefinite completion, forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G: Furthermore, the set of partial Hermitian matrices, with non-negative fully specified principal minors, also forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices which can be written as the sum of rank one matrices, with underlying graph G. Consequently, the problem reduces to determining when these cones are equal. Indeed, we find that this happens if and only if the underlying graph is chordal. It then follows that the extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G is generated by rank one matrices. The question that arises, is what happens if the underlying graph is not chordal. In particular, what can be said about the extreme rays of the cone of positive semidefinite matrices with some non-chordal pattern. This gives rise to the notion of the sparsity order of a graph G; that is, the maximum rank of matrices lying on extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G: We will see that those graphs having sparsity order less than or equal to 2 can be fully characterized. Moreover, one can determine in polynomial time whether a graph has sparsity order less than or equal to 2, using a clique-sum decomposition. We also show that one can determine whether a graph has sparsity order less than or equal to 2, by considering the characteristic polynomial of the adjacency matrix of certain forbidden induced subgraphs and comparing it with the characteristic polynomial of principal submatrices of appropriate size. / MSc (Mathematics), North-West University, Potchefstroom Campus, 2015

A partial matrix, is a matrix for which some entries are specified and some unspecified. In general completion problems ask whether a given partial matrix, may be completed to a matrix where all the entries are specified, such that this completion admits a specific structure. The positive definite completion problem asks whether a partial Hermitian matrix admits a completion such that the completed matrix is positive semidefinite. The minimum solution criterion, is that every fully specified principal submatrix is nonnegative. Then the set of partial Hermitian matrices, which admit a positive semidefinite completion, forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G: Furthermore, the set of partial Hermitian matrices, with non-negative fully specified principal minors, also forms a convex cone, and its dual cone can be identified as the set of positive semidefinite Hermitian matrices which can be written as the sum of rank one matrices, with underlying graph G. Consequently, the problem reduces to determining when these cones are equal. Indeed, we find that this happens if and only if the underlying graph is chordal. It then follows that the extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G is generated by rank one matrices. The question that arises, is what happens if the underlying graph is not chordal. In particular, what can be said about the extreme rays of the cone of positive semidefinite matrices with some non-chordal pattern. This gives rise to the notion of the sparsity order of a graph G; that is, the maximum rank of matrices lying on extreme rays of the cone of positive semidefinite Hermitian matrices with zeros in the entries that correspond to non-edges in the graph G: We will see that those graphs having sparsity order less than or equal to 2 can be fully characterized. Moreover, one can determine in polynomial time whether a graph has sparsity order less than or equal to 2, using a clique-sum decomposition. We also show that one can determine whether a graph has sparsity order less than or equal to 2, by considering the characteristic polynomial of the adjacency matrix of certain forbidden induced subgraphs and comparing it with the characteristic polynomial of principal submatrices of appropriate size. / MSc (Mathematics), North-West University, Potchefstroom Campus, 2015

In 1990, Fröberg presented a combinatorial classification of the quadratic square-free monomial ideals with linear resolutions. He showed that the edge ideal of a graph has a linear resolution if and only if the complement of the graph is chordal. Since then, a generalization of Fröberg's theorem to higher dimensions has been sought in order to classify all square-free monomial ideals with linear resolutions. Such a characterization would also give a description of all square-free monomial ideals which are Cohen-Macaulay. In this thesis we explore one method of extending Fröberg's result. We generalize the idea of a chordal graph to simplicial complexes and use simplicial homology as a bridge between this combinatorial notion and the algebraic concept of a linear resolution. We are able to give a generalization of one direction of Fröberg's theorem and, in investigating the converse direction, find a necessary and sufficient combinatorial condition for a square-free monomial ideal to have a linear resolution over fields of characteristic 2.

abstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma. / Dissertation/Thesis / Ph.D. Mathematics 2011

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study cubic graphs whose vertex set can be partitioned into two total dominating sets. There are infinitely many examples of connected cubic graphs that do not have such a vertex partition. In this paper, we show that the class of claw-free cubic graphs has such a partition. For an integer k at least 3, a graph is k-chordal if it does not have an induced cycle of length more than k. Chordal graphs coincide with 3-chordal graphs. We observe that for k≥6, not every graph in the class of k-chordal, connected, cubic graphs has two vertex disjoint total dominating sets. We prove that the vertex set of every 5-chordal, connected, cubic graph can be partitioned into two total dominating sets. As a consequence of this result, we observe that this property also holds for a connected, cubic graph that is chordal or 4-chordal. We also prove that cubic graphs containing a diamond as a subgraph can be partitioned into two total dominating sets.

No description available.

This thesis is divided into two parts. The first part is concerned with the commutative algebra of certain combinatorial structures arising from uniform hypergraphs. The main focus lies on two particular classes of hypergraphs called chordal hypergraphs and complete hypergraphs, respectively. Both these classes arise naturally as generalizations of the corresponding well known classes of simple graphs. The classes of chordal and complete hypergraphs are introduced and studied in Chapter 2 and Chapter 3 respectively. Chapter 4, that is the content of \cite{E5}, answers a question posed at the P.R.A.G.MAT.I.C. summer school held in Catania, Italy, in 2008. In Chapter 5 we study hypergraph analogues of line graphs and cycle graphs. Chapter 6 is concerned with a connectedness notion for hypergraphs and in Chapter 7 we study a weak version of shellability.The second part is concerned with affine monoids and their monoid rings. Chapter 8 provide a combinatorial study of a class of positive affine monoids that behaves in some sense like numerical monoids. Chapter 9 is devoted to the class of numerical monoids of maximal embedding dimension. A combinatorial description of the graded Betti numbers of the corresponding monoid rings in terms of the minimal generators of the monoids is provided. Chapter 10 is concerned with monomial subrings generated by edge sets of complete hypergraphs.

一個圖形G = (V,E)，如果可以找到最小k個和弦圖，則此圖形G = (V,E)的和弦圖數是k。 在這篇論文中，我們呈現存在一個系列平行圖的boxicity是3，且和弦圖數是1或2，存在一個平面圖形的和弦圖數是3。 / The chordality of G = (V,E) is dened as the minimum k such that we can write E = E1n...nEk, where each (V,Ei) is a chordal graph. In this thesis, we present that (1) there are series-parallel graphs with boxicity 3, (2) there are series-parallel graphs with chordality 1 or 2, and (3) there are planar graphs with chordality 3.

Cette thèse propose une nouvelle méthode pour fournir une connexion réseau à des véhicules au cours de trajets prédéterminés (trains, métros, autobus urbains, etc.). La communication entre le véhicule et l'infrastructure réseau est basée uniquement sur la technologie WiFi. Les contributions de ce travail sont d'une part la conception d'une méthode pour réaliser le handover horizontal (entre bornes WiFi), et d'autre part la modélisation et l'analyse de topologies pour le réseau d'infrastructure (réseau backbone plus réseau d'accès WiFi) déployé sur la trajectoire du véhicule. Dans une première partie, nous proposons une méthode, appelée Spiderman Handover, pour réaliser le handover horizontal d'un réseau en mouvement (embarqué dans le véhicule) et une procédure de mise à jour des informations de routage (couche 2 OSI) lors du handover. Nous évaluons notre proposition par simulation et validons nos résultats par des mesures expérimentales. Dans une deuxième partie, nous étudions théoriquement les paramètres de plusieurs familles de topologies du type Chordal pour le réseau backbone construit sur un réseau d'accès linéaire. A partir de la comparaison de ces paramètres, nous proposons une topologie backbone issue de la combinaison de deux topologies Chordal. Cette topologie fournit un bon compromis entre coût du déploiement, nombre de sauts nécessaires pour atteindre la passerelle du réseau et résilience raisonnable. Enfin, nous évaluons l'intégration de la topologie proposée pour le réseau d'infrastructure avec le système handover par des simulations. Les résultats présentés suggèrent que l'algorithme de handover proposé fonctionne correctement sur le réseau d'infrastructure proposé. Cela permet la garantie d'une connexion continue aux passagers à bord des trains, métros ou autobus urbains.