There is an emerging need to develop new techniques for control system design that better address the challenges posed by modern large-scale cyber-physical systems. These systems are often massive networks of interconnected and interoperating subsystems that fuse physical processes, embedded computation, automation technologies, and communication. The resulting problems are dimensionally large, exhibit significant time-varying structural variations during operation, and feature complex dynamics, constraints and objectives across local and global-system scales. These properties are difficult to address using traditional control theoretic methods without substantial loss of performance and robustness. To overcome these limitations, this dissertation presents new concepts and methods for control of modern large-scale variably-structured systems through self-assembling and self-configuring control constructs that allow for fundamental restructuring of the control system’s topology in response to the current system structure. We present the System Component Graph (SCG) formulation as a mathematical framework that generalizes and extends directed graph methods from decentralized control. We present algorithms, methods, and metrics for real-time decentralization and control-structure optimization, utilizing the inclusion principle for addressing interconnected overlapping dynamics and optimal linear-quadratic (LQ) methods for local decentralized subsystem control. Global system control and performance is achieved through a centralized planner that provides continuous real-time optimized trajectories as guidance command inputs to each subsystem. We present the method of Random Subcomplement Trees (RST) for pseudo-optimal real-time trajectory planning of large-scale systems which formalizes and extends the method of rapidly-exploring random trees in a control optimization framework. The RST method defines transformations from the higher-dimension state space into an intermediate lower-dimensional search space, where optimal transitions between subspace states are defined. In the context of this approach, the resulting decentralized topology found within the SCG framework provides the RST subspace definition and requisite transformations, and optimal transitions in the search space are found through forward evaluation of the closed-loop decentralized subsystem dynamics. The methods developed in this thesis are applied to a set of real-world problems spanning various domains and demonstrate the application of these methods from first-principle modeling through control system analysis, design, implementation, and evaluation in experimental tests and simulation.

A path π = (v1, v2,...vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 < i < k, deg(vi) > deg(vi+1), where deg(vi) denotes the degree of vertex vi ∊ V. The downhill domination number equals the minimum cardinality of a set S ⊂ V having the property that every vertex v ∊ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds.

Graphs can effectively model biomolecules, computer systems, and other applications. A weighted graph is a graph in which values or labels are assigned to the edges of the graph. However, in this thesis, we assign values to the vertices of the graph rather than the edges and we modify several standard graphical measures to incorporate these vertex weights. In particular, we designate the degree of each vertex as its weight. Previous research has not investigated weighting vertices by degree. We find the vertex weighted domination number in connected graphs, beginning with trees, and we define how weighted vertices can affect eccentricity, independence number, and connectivity.

For a graph G = (V,E), we consider a bipartition {V1,V2} of the vertex set V by placing constraints on the vertices as follows. For every vertex v in Vi, we place a constraint on the number of neighbors v has in Vi and a constraint on the number of neighbors it has in V3-i. Using three values, namely 0 (no neighbors are allowed), 1 (at least one neighbor is required), and X (any number of neighbors are allowed) for each of the four constraints, results in 27 distinct types of bipartitions. The goal is to characterize graphs having each of these 27 types. We give characterizations for 21 out of the 27. Three other characterizations appear in the literature. The remaining three prove to be quite difficult. For these, we develop properties and give characterization of special families.

If every vertex in a graph G has the same degree, then the graph is called a regular graph. That is, if deg(v) = r for all vertices in the graph, then it is denoted as an r-regular graph. A graph G is said to be vertex-weighted if all of the vertices are assigned weights. A generalized definition for degree regularity for vertex-weighted graphs can be stated as follows: A vertex-weighted graph is said to be rw-regular if the sum of the weights in the neighborhood of every vertex is rw. If all vertices are assigned the unit weight of 1, then this is equivalent to the definition for r-regular graphs. In this thesis, we determine if a graph has a weighting scheme that makes it a weighted regular graph or prove no such scheme exists for a number of special classes of graphs such as paths, stars, caterpillars, spiders and wheels.

Several challenges face bioinformaticians on a regular basis. One of these is unsupervised clustering. In RNA sequencing (RNAseq), this may come in the form of blindly sequencing single cells without a priori knowledge of the cell types being sequenced. Here we create new methods to address this problem that show increased accuracy and speed compared to competing methods. We also have developed a methodology for discovering non-parametric networks which represent relationships between the variables that have been measured across samples. In the context of RNAseq, this is the expression relationships between genes (for example a positive or negative Spearman correlation). We have packaged these techniques into a software tool called PyMINEr. We show the implementation of PyMINEr here in the analysis of single cell RNAseq (scRNAseq), and integrate this dataset with others to yield novel insights to the signaling networks among within and between pancreatic islet cell types. Additionally we used this data to predict the cell type specific importance of Type 2 Diabetes (T2D) single nucleotide polymorphisms (SNPs). Lastly we have demonstrated the use of PyMINEr’s analytic techniques in discovering genetic circuitry underlying the transcriptional networks of two transcription factors (NeuroD1 and Pdx1) in beta cells. We utilized a RNA interference to modulate the expression of these transcription factors in a beta cell line (MIN6), and observe the changes in the transcriptome over time. We used this data to generate graph network models of transcription and integrated them with ChIP-seq of these transcription factors; this enabled annotation of the functional binding sites of these transcription factors. Furthermore, this approach has enabled the discovery of regulators of beta and alpha cell identity. Overall, we have developed novel informatics methods which can be applied to complex datasets to guide bench experiments towards to discovery of molecular signaling networks.

The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.

Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleurs. / This thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo

Hadwiger's conjecture is one of the deepest open questions in graph theory, and Cayley graphs are an applicable and useful subtopic of algebra. Chapter 1 will introduce Hadwiger's conjecture and Cayley graphs, providing a summary of background information on those topics, and continuing by introducing our problem. Chapter 2 will provide necessary definitions. Chapter 3 will give a brief survey of background information and of the existing literature on Hadwiger's conjecture, Hamiltonicity, and the isoperimetric number; in this chapter we will explore what cases are already shown and what the most recent results are. Chapter 4 will give our decomposition theorem about PSL2 (R). Chapter 5 will continue with corollaries of the decomposition theorem, including showing that Hadwiger's conjecture holds for our Cayley graphs. Chapter 6 will finish with some interesting examples.

In July 2012, a paper by Gutfraind et al. introduced the neighbor-aided network installation problem, which asks for "a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited." Additionally, in a 2018 paper by Cummings et al., two greedy heuristics were implemented to estimate solutions to the NANIP-Blackstart problem. This paper will evaluate the performance of the greedy heuristics introduced by Cummings et al., and compare their performance to a new heuristic. In addition to comparing heuristics, we will also look at varying the blackstart node and cost function. This analysis will be conducted by testing the heuristics on power networks from the SuiteSparse Matrix Collection and NIST Matrix Market. The goal of this body of work is to better understand the variables at play in the NANIP-Blackstart problem in order to work towards better estimated solutions.