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.

Cēgə Trouhèst is a three-movement work of about thirteen minutes duration. The text by the composer provides a vehicle for aural stimulation only. Cēgə Trouhèst is a continuum of resonances embellished by melodic and rhythmic passages. These embellishments along with other devices and the choice of instrumentation all contribute to the development of the varied timbres. The first two movements introduce the material to be employed in the third, which continues the idea of change exhibited in the text by modification and extraction. Timbre is the most important aspect of this work. It is exploited homophonically, contrapuntally, and through instrumental/vocal interchange and timbre modification of a single tone.

The topic of this thesis is black virus disinfection using mobile agents. The black virus is a faulty node that destroys any visiting agent without leaving a trace; moreover, once the black virus is triggered by an agent, it clones itself and spreads to neighbouring nodes. These viruses can only be destroyed if they move to nodes that have been occupied by agents. In this thesis, we consider the black virus disinfection problem in chordal rings. Initially, the system contains a single black virus that resides at an unknown location. We propose a solution that involves deploying a team of mobile agents to locate the original black virus and to prevent further damage once it has been triggered. Our protocol is divided into two phases: 1) searching the graph until the black virus is found and triggered and 2) sending agents to occupy the neighbouring nodes of the black virus in order to trigger and destroy all the black viruses at once. Our solutions are monotone, meaning that once a node has been explored it is protected from re-infection. In order to measure the efficiency of our protocol we consider the total number of agents required for disinfection, the overall number of black viruses and the number of moves required by the agents. We then analyze the cost of all our solutions, providing optimal bounds for some classes of chordal rings.

Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoint paths for each pair of processes without direct connection to tolerate failures (where t is the maximum number of processes that may crash and n is the total number of processes), can be applied to solve the GDC problem in the chordal but the virtual links approach incurs high message complexity. To reduce the high communication cost, we propose a non round-based GDC protocol for the asynchronous chordal ring with perfect failure detectors. The main advantage of our approach is that there is no notion of round, processes only send messages via direct connections and the implementation of failure detectors does not require process-disjoint paths. Analysis and comparison with the virtual links approach shows that our protocol reduces the message complexity significantly. / Singapore-MIT Alliance (SMA)

The topic of this thesis is black virus disinfection using mobile agents. The black virus is a faulty node that destroys any visiting agent without leaving a trace; moreover, once the black virus is triggered by an agent, it clones itself and spreads to neighbouring nodes. These viruses can only be destroyed if they move to nodes that have been occupied by agents. In this thesis, we consider the black virus disinfection problem in chordal rings. Initially, the system contains a single black virus that resides at an unknown location. We propose a solution that involves deploying a team of mobile agents to locate the original black virus and to prevent further damage once it has been triggered. Our protocol is divided into two phases: 1) searching the graph until the black virus is found and triggered and 2) sending agents to occupy the neighbouring nodes of the black virus in order to trigger and destroy all the black viruses at once. Our solutions are monotone, meaning that once a node has been explored it is protected from re-infection. In order to measure the efficiency of our protocol we consider the total number of agents required for disinfection, the overall number of black viruses and the number of moves required by the agents. We then analyze the cost of all our solutions, providing optimal bounds for some classes of chordal rings.

No description available.

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.

Chordal graphs are an important class of perfect graphs. The beautiful theory surrounding their study varies from natural applications to elegant characterizations in terms of forbidden subgraphs, subtree representations, vertex orderings, and to linear time recognition algorithms. Haskins and Rose introduced the class of chordal digraphs as a digraph analogue of chordal graphs. Chordal digraphs can be defined in terms of vertex orderings and several results about chordal graphs can be extended to chordal digraphs. However, a forbidden subdigraph characterization of chordal digraphs is not known and finding such a characterization seems to be a difficult problem. Meister and Telle studied semi-complete chordal digraphs and gave a forbidden subdigraph characterization of this class of digraphs. In this thesis, we study chordal digraphs within the classes of quasi-transitive, extended semi-complete, and locally semi-complete digraphs. For each of these classes we obtain a forbidden subdigraph characterization of digraphs which are chordal. We also introduce in this thesis a new variant of chordal digraphs called semi-strict chordal digraphs. We obtain a forbidden subdigraph characterization of semi-strict chordal digraphs for each of the classes of semi-complete, quasi-transitive, extended semi-complete, and locally semi-complete digraphs. / Graduate