Fricke, Haynes, Hedetniemi, Hedetniemi, and Laskar introduced the following concept. For a graph G = (V,E), let rho denote a property of interest concerning sets of vertices. A vertex u is rho-good if u is contained in a {minimum, maximum} rho-set in G and rho-bad if u is not contained in a rho-set. Let g denote the number of rho-good vertices and b denote the number of rho-bad vertices. A graph G is called rho-excellent if every vertex in V is rho-good, rho-commendable if g > b > 0, rho-fair if g = b, and rho-poor if g < b. In this thesis the property of interest is total domination. The total domination number, gammat, is the cardinality of a smallest total dominating set in a graph. We investigate gammat-excellent, gammat-commendable, gammat-fair, and gammat-poor graphs.

The game "Generalized Kayles (or Independence Achievement)" is played by two players A and B on an arbitrary graph G. The players alternate removing a vertex and its neighbors from G, the winner being the last player with a nonempty set from which to choose. In this thesis, we present winning strategies for some paths.

Let S ⊆ V be an arbitrary subset of vertices of a graph G = (V,E). The differential ∂(S) equals the difference between the cardinality of the set of vertices not in S but adjacent to vertices in S, and the cardinality of the set S. The differential of a graph G equals the maximum differential of any subset S of V . A set S is called a zero set if ∂(S) = 0. In this thesis we introduce the study of zero sets in graphs. We give proofs of the existence of zero sets in various kinds of graphs such as even order graphs, bipartite graphs, and graphs of maximum degree 3. We also give proofs regarding the existence of graphs which contain no zero sets and the construction of zero-free graphs from graphs which contain zero sets.

No description available.

The energy of a graph began with German physicist, Erich H¨uckel’s 1931 paper, Quantenttheoretische Beitr¨age zum Benzolproblem. His work developed a method for computing the binding energy of the π-electrons for a certain class of organic molecules. The vertices of the graph represented the carbon atoms while the single edge between each pair of distinct vertices represented the hydrogen bonds between the carbon atoms. In turn, the chemical graphs were represented by an n × n matrix used in solving Schr¨odinger’s eigenvalue/eigenvector equation. The sum of the absolute values of these graph eigenvalues represented the total π-electron energy. The criteria for constructing these chemical graphs and the chemical interpretations of all the quantities involved made up the H¨uckel Molecular Orbital theory or HMO theory. In this paper, we will show how the chemical interpretation of H¨uckel’s graph energy evolved to a mathematical interpretation of graph energy that Ivan Gutman provided for us in his famous 1978 definition of the energy of a graph. Next, we will present Charles Coulson’s 1940 theorem that expresses the energy of a graph as a contour integral and prove some of its corollaries. These corollaries allow us to order the energies of acyclic and bipartite graphs by the coefficients of their characteristic polynomial. Following Coulson’s theorem and its corollaries we will look at McClelland’s first theorem on the bounds for the energy of a graph. In the corollaries that follow McClelland’s 1971 theorem, we will prove the corollaries that show a direct variation between the energy of a graph and the number of its vertices and edges. Finally, we will see how this relationship led to Gutman’s conjecture that the complete graph on n vertices has maximal energy. Although this was disproved by Chris Godsil in 1981, we will provide an independent counterexample with the help of the software, Maple 13

Microorganisms are key players in the ecosystem functioning. In this thesis, we developed a framework to preprocess raw microbiome data, build a correlation network, and analyze co-occurrence patterns between microbes. We then applied this framework to a marine microbiome dataset. The dataset used in this study comes from a year-long time-series to characterize the microbial communities in our coastal waters off the Cal Poly Pier. In analyzing this dataset, we were able to observe and confirm previously discovered patterns of interactions and generate hypotheses about new patterns. The analysis of co-occurrences between prokaryotic and eukaryotic taxa is relatively novel and can provide new insight into how marine microbial communites are structured and interact.

Congenital heart disease (CHD) is the most common congenital anomaly, with single ventricle (SV) defects accounting for nearly 10% of all CHD. SV defects tend to be the most severe forms of CHD: all patients born with SV require multiple open heart surgeries, often beginning in the neonatal period, ultimately leading to the Fontan procedure. Due to improvements in surgical procedures and medical care, more patients are surviving into adolescence and adulthood. Brain imaging and pathology studies have shown that patients with SV have differences in brain structure and metabolism even before the first surgery, and as early as in utero. Furthermore, a significant number of patients have new or more severe lesions after the initial surgery, and many still have brain abnormalities into early childhood. However, there are no detailed brain structural data of SV patients in adolescence. Our group recruited a large cohort of post-Fontan SV patients aged 10-19 years. Separate analyses of neuropsychological and behavioral outcomes in these patients show deficits in multiple areas of cognition, increased rates of attention deficit-hyperactivity disorder (ADHD), and increased use of remedial and/or special education services compared to a control group. Post-Fontan adolescents have more gross brain abnormalities, including evidence of chronic ischemic stroke. Furthermore, there are widespread reductions in cortical and subcortical gray matter volume and cortical thickness, some of which are associated with medical and surgical variables. Diffusion tensor imaging (DTI) analyses show widespread areas of altered white matter microstructure in deep subcortical and cerebellar white matter. In this dissertation, I use graph theory methods to characterize structural connectivity based on gray matter (cortical thickness covariance) and white matter (DTI tractography), and examine associations between brain structure and neurodevelopment. I found that brain network connectivity differs in post-Fontan patients compared with controls, both at the global and regional level. Additionally, deficits in overall network structure were associated with impaired neurodevelopment in several domains, including general intelligence, executive function, and visuospatial skills. These data suggest that early neuroprotection should be a major focus in the care of SV patients, with the goal of improving long-term neurodevelopmental outcomes.

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. If one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. All such safe walks were recently characterized as omnitigs, leading to the first safe and complete genome assembly algorithm. Even if omnitig finding was improved to quadratic time, it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We describe an O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig, with two consequences: a linear-time output sensitive algorithm enumerating all maximal omnitigs and a compact O(m) representation of all maximal omnitigs. This safe and complete genome assembly algorithm was followed by other works improving the time bounds, as well as extending the results for different notions of assembly solution. But it remained open whether one can be complete also for models of genome assembly of practical applicability. In this dissertation, we also present a universal framework for obtaining safe and complete algorithms which unify the previous results, while also allowing to characterize different assembly problems. This is based on a novel graph structure, called the hydrostructure of a walk, which highlights the reachability properties of the graph from the perspective of the walk. Almost all of our characterizations are directly adaptable to optimal verification algorithms, and simple enumeration algorithms. Most of these algorithms are also improved to optimality using an incremental computation procedure and a previous optimal algorithm of a specific model.

Hadwiger's Conjecture from 1943 states that every graph with no Kt minor is (t-1)-colorable; it remains wide open for t ≥ 7. For positive integers t and s, let Kt-s denote the family of graphs obtained from the complete graph Kt by removing s edges. We say that a graph has no Kt-s minor if it has no H minor for every H in Kt-s. In 1971, Jakobsen proved that every graph with no K7-2 minor is 6-colorable. In this dissertation, we first study the extremal functions for K8-4 minors, K9-6 minors, and K10-12 minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K8-4 minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K9-6 minor, and every graph on n ≥ 10 vertices with at least 5.5n-17.5 edges has a K10-12 minor. We then prove that every graph with no K8-4 minor is 7-colorable, every graph with no K9-6 minor is 8-colorable, and every graph with no K10-12 minor is 9-colorable. The proofs use the extremal functions as well as generalized Kempe chains of contraction-critical graphs obtained by Rolek and Song and a method for finding minors from three different clique subgraphs, originally developed by Robertson, Seymour, and Thomas in 1993 to prove Hadwiger's Conjecture for t = 6. Our main results imply that H-Hadwiger's Conjecture is true for each graph H on 8 vertices that is a subgraph of every graph in K8-4, each graph H on 9 vertices that is a subgraph of every graph in K9-6, and each graph H on 10 vertices that is a subgraph of every graph in K10-12.

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G → (H1, ..., Hk), or G → (H)k when H1 = ··· = Hk = H, if every k-edge-coloring of G contains a monochromatic Hi in color i for some i ∈ {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn → (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edge-colorings with no rainbow triangles. From this we define the Gallai-Ramsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn → (G)k . In this thesis, we determine the Gallai-Ramsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ≥ 2, where C2n+1 denotes a cycle on 2n + 1 vertices.