Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Entire DC Network
Grim Under A Compensation Variant, Aaron Davis, Aaron Davis
Grim Under A Compensation Variant, Aaron Davis, Aaron Davis
Honors College Theses
Games on graphs are a well studied subset of combinatorial games. Balance and strategies for winning are often looked at in these games. One such combinatorial graph game is Grim. Many of the winning strategies of Grim are already known. We note that many of these winning strategies are only available to the first player. Hoping to develop a fairer Grim, we look at Grim played under a slighlty different rule set. We develop winning strategies and known outcomes for this altered Grim. Throughout, we discuss whether our altered Grim is a fairer game then the original.
Decompositions Of The Complete Mixed Graph By Mixed Stars, Chance Culver
Decompositions Of The Complete Mixed Graph By Mixed Stars, Chance Culver
Electronic Theses and Dissertations
In the study of mixed graphs, a common question is: What are the necessary and suffcient conditions for the existence of a decomposition of the complete mixed graph into isomorphic copies of a given mixed graph? Since the complete mixed graph has twice as many arcs as edges, then an obvious necessary condition is that the isomorphic copies have twice as many arcs as edges. We will prove necessary and suffcient conditions for the existence of a decomposition of the complete mixed graphs into mixed stars with two edges and four arcs. We also consider some special cases of decompositions …
Dna Complexes Of One Bond-Edge Type, Andrew Tyler Lavengood-Ryan
Dna Complexes Of One Bond-Edge Type, Andrew Tyler Lavengood-Ryan
Electronic Theses, Projects, and Dissertations
DNA self-assembly is an important tool used in the building of nanostructures and targeted virotherapies. We use tools from graph theory and number theory to encode the biological process of DNA self-assembly. The principal component of this process is to examine collections of branched junction molecules, called pots, and study the types of structures that such pots can realize. In this thesis, we restrict our attention to pots which contain identical cohesive-ends, or a single bond-edge type, and we demonstrate the types and sizes of structures that can be built based on a single characteristic of the pot that is …
A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler
A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler
Senior Independent Study Theses
Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.
Phylogenetic Networks And Functions That Relate Them, Drew Scalzo
Phylogenetic Networks And Functions That Relate Them, Drew Scalzo
Williams Honors College, Honors Research Projects
Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …
Extremal/Saturation Numbers For Guessing Numbers Of Undirected Graphs, Jo Ryder Martin
Extremal/Saturation Numbers For Guessing Numbers Of Undirected Graphs, Jo Ryder Martin
Graduate College Dissertations and Theses
Hat guessing games—logic puzzles where a group of players must try to guess the color of their own hat—have been a fun party game for decades but have become of academic interest to mathematicians and computer scientists in the past 20 years. In 2006, Søren Riis, a computer scientist, introduced a new variant of the hat guessing game as well as an associated graph invariant, the guessing number, that has applications to network coding and circuit complexity. In this thesis, to better understand the nature of the guessing number of undirected graphs we apply the concept of saturation to guessing …
A Computational Study Of Binary Linear And Quadratic Programming And Solvers, William Cody Mackelfresh
A Computational Study Of Binary Linear And Quadratic Programming And Solvers, William Cody Mackelfresh
Graduate Research Theses & Dissertations
In this thesis we study and compare computational capability of two solvers, Gurobi and BiqCrunch, and their capabilities to solve various binary quadratic and linear programming problems. We review two types of programming models for three types of combinatorial optimization problems, namely Max-Cut, Max Independent Set, and Max-$k$-Cluster. We also review the Reformulation-Linearization Technique (RLT) and Semidefinite Programming (SDP) approaches for solving these models, go over the software and hardware used to solve these problems, and finally review the numerical results obtained by solving the problems.
Laplacian Spectra Of Kneser-Like Bipartite Graphs, Cesar Iram Vazquez
Laplacian Spectra Of Kneser-Like Bipartite Graphs, Cesar Iram Vazquez
Open Access Theses & Dissertations
Given a,b ∈N such that a > b we define a Kneser-like bipartite graph G(a,b), whose two bipartite sets of vertices represent the a-subsets and b-subsets of S = {1,...,a + b + 1}, and whose edges are pairs of vertices X and Y such that X ∩Y = ∅. We prove that the eigenvalues of the Laplacian matrix of graphs G(a,1) are all nonnegative integers. In fact, we describe these eigenvalues, and their respective multiplicities.