Both chordal and weakly chordal graphs have been topics of research in graph theory for many years. Upon reading their definitions it is clear that the weakly chordal class of graphs is a relaxation of the chordal condition for graphs. The question is then asked could we possibly find and study the properties if we, in turn, relaxed the weakly chordal condition for graphs? We start by providing the definitions and basic results needed later on. In the second chapter, we discuss perfect graphs, some of their properties, and some subclasses that were researched. The third chapter is focused on a new class of graphs, the definition of which relaxes the restrictions for chordal and weakly chordal graphs, and extends certain results from weakly chordal graphs to this class.

No description available.

Let G be a graph and f be a function that maps V to {0,1,2, ..., diam(G)}. Let V+ be the set of all vertices such that f(v) is positive. If for every vertex v not in V+ there exists a vertex w in V+ such that the distance between v and w is at most f(w), then f is called a dominating broadcast of G. The cost of the broadcast f is the sum of the values f(v) over all vertices v in V. The minimum cost of a dominating broadcast is called the broadcast domination number of G. A subset S of V is a multipacking if, for every v in V and for every integer k which is at least 1 and at most rad(G), the set S contains at most k vertices at distance at most k from v. The multipacking number of G is the maximum cardinality of a multipacking of G. In the first part of the thesis, we describe how linear programming can be used to give a cubic algorithm to find the broadcast domination number and multipacking number of strongly chordal graphs. Next, we restrict attention to trees, and describe linear time algorithms to compute these numbers. Finally, we introduce k-broadcast domination and k-multipacking, develop the basic theory and give a bound for the 2-broadcast domination number of a tree in terms of its order. / Graduate

In this thesis we investigate how the properties of chordal graphs can be used to exploit sparsity in several optimisation problems that arise in control theory. In particular, we focus on analysis and synthesis problems that involve semidefinite constraints and can be formulated as semidefinite programming (SDP) problems. Using a relationship between chordal graphs and sparse semidefinite matrices, we decompose the semidefinite constraints in the associated SDP problems into multiple, smaller semidefinite constraints along with some additional equality constraints. The benefit of this approach is that for sparse dynamical systems we can solve significantly larger analysis and synthesis problems than is possible using traditional dense methods. We begin by considering the properties of chordal graphs and their connection to sparse positive semidefinite matrices. We then turn our attention to the problem of constructing Lyapunov functions for linear time-invariant (LTI) systems. From this starting point, we derive methods of exploiting chordal sparsity in other analysis problems found in control theory. In particular, this approach is applied to the problem of bounding the input-output properties of systems via the KYP lemma for both continuous and discrete-time systems. We then consider how the properties of chordal graphs can be exploited in the SDPs that arise in static state feedback controller synthesis problems for LTI systems. We show that the sparse inverse property of the maximum determinant completion of a partial positive matrix can be used to design controllers with a pre-specified sparsity pattern. We then consider how to exploit chordal sparsity when designing a static state feedback controller to minimise the H-infinity norm of an LTI system. Next we shift from linear systems to nonlinear systems and develop a chordal sparsity approach to scalable stability analysis of systems with polynomial dynamics using the Sums of Squares (SOS) technique. We develop a method of exploiting chordal sparsity that avoids the computationally costly step of forming the coefficient matrix in the SOS problem. We then apply this method to the problem of constructing Lyapunov functions for systems with correlatively sparse polynomial vector fields. Finally, we conclude by discussing some directions for future research.

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

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.

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.

一個圖形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.