Discrete Mathematics and Combinatorics Commons^™

Dna Self-Assembly Of Trapezohedral Graphs, Hytham Abdelkarim

Electronic Theses, Projects, and Dissertations

Self-assembly is the process of a collection of components combining to form an organized structure without external direction. DNA self-assembly uses multi-armed DNA molecules as the component building blocks. It is desirable to minimize the material used and to minimize genetic waste in the assembly process. We will be using graph theory as a tool to find optimal solutions to problems in DNA self-assembly. The goal of this research is to develop a method or algorithm that will produce optimal tile sets which will self-assemble into a target DNA complex. We will minimize the number of tile and bond-edge types …

Waste Treatment Facility Location For Hotel Chains, Dolores R. Santos-Peñate, Rafael R. Suárez-Vega, Carmen Florido De La Nuez

ITSA 2022 Gran Canaria - 9th Biennial Conference: Corporate Entrepreneurship and Global Tourism Strategies After Covid 19

Tourism generates huge amounts of waste. About half of the waste generated by hotels is food and garden bio-waste. This bio-waste can be used to make compost and pellets. In turn, pellets can be used as an absorbent material in composters and as an energy source. We consider the problem of locating composting and pellet-making facilities so that the bio-waste generated by a chain of hotels can be managed at or close to the generation points. An optimization model is applied to locate the facilities and allocate the waste and products, and several scenarios are analysed. The study shows that, …

A Bit-Parallel Tabu Search Algorithm For Finding Es2 -Optimal And Minimax-Optimal Supersaturated Designs, Luis B. Morales, Dursun A. Bulotuglu

Faculty Publications

We prove the equivalence of two-symbol supersaturated designs (SSDs) with N (even) rows, m columns, s_max=4t+i, where i ∈ {0,2}, t ∈ Z^≥0 and resolvable incomplete block designs (RIBDs) whose any two blocks intersect in at most (N+4t+i)/4 points. Using this equivalence, we formulate the search for two-symbol E(s²)-optimal and minimax-optimal SSDs with s_max ∈ {2,4,6} as a search for RIBDs whose blocks intersect accordingly. This allows developing a bit-parallel tabu search (TS) algorithm. The TS algorithm found E(s²)-optimal and minimax-optimal SSDs achieving the sharpest known E(s²) lower bound with …

A Pebbling Game On Powers Of Paths, Garth Isaak, Matthew Prudente, Joseph M. Marcinik Iii

Communications on Number Theory and Combinatorial Theory

Two Player Graph Pebbling is an extension of graph pebbling. Players Mover and Defender use pebbling moves, the act of removing two pebbles from one vertex and placing one pebble on an adjacent vertex, to win. If a specified vertex has a pebble on it, then Mover wins. If a specified vertex is pebble-free and there are no more valid pebbling moves, then Defender wins. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement of m pebbles and for any specified vertex, Mover can win. We specify the …

A Survey On Online Matching And Ad Allocation, Ryan Lee

Theses

One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …

Complex-Valued Approach To Kuramoto-Like Oscillators, Jacqueline Bao Ngoc Doan

Electronic Thesis and Dissertation Repository

The Kuramoto Model (KM) is a nonlinear model widely used to model synchrony in a network of oscillators – from the synchrony of the flashing fireflies to the hand clapping in an auditorium. Recently, a modification of the KM (complex-valued KM) was introduced with an analytical solution expressed in terms of a matrix exponential, and consequentially, its eigensystem. Remarkably, the analytical KM and the original KM bear significant similarities, even with phase lag introduced, despite being determined by distinct systems. We found that this approach gives a geometric perspective of synchronization phenomena in terms of complex eigenmodes, which in turn …

Decomposition Of Beatty And Complementary Sequences, Geremías Polanco

Mathematics and Statistics: Faculty Publications

In this paper we express the difference of two complementary Beatty sequences, as the sum of two Beatty sequences closely related to them. In the process we introduce a new Algorithm that generalizes the well known Minimum Excluded algorithm and provides a method to generate combinatorially any pair of complementary Beatty sequences.

Δ-Small Intersection Graphs Of Modules, Ahmed H. Alwan

Al-Bahir Journal for Engineering and Pure Sciences

Let R be a commutative ring with unit and M be a unitary left R-module. The δ-small intersection graph of non-trivial submodules of , denoted by , is an undirected simple graph whose vertices are the non-trivial submodules of , and two vertices are adjacent if and only if their intersection is a -small submodule of . In this article, we study the interplay between the algebraic properties of , and the graph properties of such as connectivity, completeness and planarity. Moreover, we determine the exact values of the diameter and girth of , as well as give a formula …

Partitions Of R^N With Maximal Seclusion And Their Applications To Reproducible Computation, Jason Vander Woude

Dissertations, Theses, and Student Research Papers in Mathematics

We introduce and investigate a natural problem regarding unit cube tilings/partitions of Euclidean space and also consider broad generalizations of this problem. The problem fits well within a historical context of similar problems and also has applications to the study of reproducibility in randomized computation.

Given $k\in\mathbb{N}$ and $\epsilon\in(0,\infty)$, we define a $(k,\epsilon)$-secluded unit cube partition of $\mathbb{R}^{d}$ to be a unit cube partition of $\mathbb{R}^{d}$ such that for every point $\vec{p}\in\R^d$, the closed $\ell_{\infty}$ $\epsilon$-ball around $\vec{p}$ intersects at most $k$ cubes. The problem is to construct such partitions for each dimension $d$ with the primary goal of minimizing …

Uconn Baseball Batting Order Optimization, Gavin Rublewski, Gavin Rublewski

Honors Scholar Theses

Challenging conventional wisdom is at the very core of baseball analytics. Using data and statistical analysis, the sets of rules by which coaches make decisions can be justified, or possibly refuted. One of those sets of rules relates to the construction of a batting order. Through data collection, data adjustment, the construction of a baseball simulator, and the use of a Monte Carlo Simulation, I have assessed thousands of possible batting orders to determine the roster-specific strategies that lead to optimal run production for the 2023 UConn baseball team. This paper details a repeatable process in which basic player statistics …

Automorphisms Of A Generalized Quadrangle Of Order 6, Ryan Pesak

Undergraduate Honors Theses

In this thesis, we study the symmetries of the putative generalized quadrangle of order 6. Although it is unknown whether such a quadrangle Q can exist, we show that if it does, that Q cannot be transitive on either points or lines. We first cover the background necessary for studying this problem. Namely, the theory of groups and group actions, the theory of generalized quadrangles, and automorphisms of GQs. We then prove that a generalized quadrangle Q of order 6 cannot have a point- or line-transitive automorphism group, and we also prove that if a group G acts faithfully on …

Reverse Mathematics Of Ramsey's Theorem, Nikolay Maslov

Electronic Theses, Projects, and Dissertations

Reverse mathematics aims to determine which set theoretic axioms are necessary to prove the theorems outside of the set theory. Since the 1970’s, there has been an interest in applying reverse mathematics to study combinatorial principles like Ramsey’s theorem to analyze its strength and relation to other theorems. Ramsey’s theorem for pairs states that for any infinite complete graph with a finite coloring on edges, there is an infinite subset of nodes all of whose edges share one color. In this thesis, we introduce the fundamental terminology and techniques for reverse mathematics, and demonstrate their use in proving Kőnig's lemma …

Cohen-Macaulay Properties Of Closed Neighborhood Ideals, Jackson Leaman

All Theses

This thesis investigates Cohen-Macaulay properties of squarefree monomial ideals, which is an important line of inquiry in the field of combinatorial commutative algebra. A famous example of this is Villareal’s edge ideal [11]: given a finite simple graph G with vertices x1, . . . , xn, the edge ideal of G is generated by all the monomials of the form xixj where xi and xj are adjacent in G. Villareal’s characterization of Cohen-Macaulay edge ideals associated to trees is an often-cited result in the literature. This was extended to chordal and bipartite graphs by Herzog, Hibi, and Zheng in …

The Italian Domatic Number On Varying Graph Families, Keith Gallegos

Scholar Week 2016 - present

See file download option for presentation.

.pdf of abstract, which contains mathematical formulas, is available as a "Supplemental File" below.

Bounds For The Augmented Zagreb Index, Ren Qingcuo, Li Wen, Suonan Renqian, Yang Chenxu

Theory and Applications of Graphs

The augmented Zagreb index (\rm{AZI} for short) of a graph $G$, introduced by Furtula et al. in 2010, is defined as ${\rm AZI}(G)=\sum\limits_{v_iv_j\in E(G)}{\left(\frac{d(v_i)d(v_j)}{d(v_i)+d(v_j)-2}\right)}^3$, where $E(G)$ is the edge set of $G$, and $d(v_i)$ denotes the degree of the vertex $v_i$. In this paper, we give some new bounds on general connected graphs, molecular trees and triangle-free graphs. \\[2mm] {\bf Keywords:} Agumented Zagreb index; molecular trees; Triangle-free graph

New Diagonal Graph Ramsey Numbers Of Unicyclic Graphs, Richard M. Low, Ardak Kapbasov

Theory and Applications of Graphs

Grossman conjectured that $R(G, G) = 2 \cdot |V(G)| - 1$, for all simple connected unicyclic graphs $G$ of odd girth and $|V(G)| \geq 4$. In this note, we prove his conjecture for various classes of $G$ containing a triangle. In addition, new diagonal graph Ramsey numbers are calculated for some classes of simple connected unicyclic graphs of even girth.

Ts-Reconfiguration Of $K$-Path Vertex Covers In Caterpillars For $K \Geq 4$, Duc A. Hoang

Theory and Applications of Graphs

A $k$-path vertex cover ($k$-PVC) of a graph $G$ is a vertex subset $I$ such that each path on $k$ vertices in $G$ contains at least one member of $I$. Imagine that a token is placed on each vertex of a $k$-PVC. Given two $k$-PVCs $I, J$ of a graph $G$, the \textsc{$k$-Path Vertex Cover Reconfiguration ($k$-PVCR)} under Token Sliding ($\mathsf{TS}$) problem asks if there is a sequence of $k$-PVCs between $I$ and $J$ where each intermediate member is obtained from its predecessor by sliding a token from some vertex to one of its unoccupied neighbors. This problem is known …

Ramsey Numbers For Connected 2-Colorings Of Complete Graphs, Mark Budden

Theory and Applications of Graphs

In 1978, David Sumner introduced a variation of Ramsey numbers by restricting to $2$-colorings in which the subgraphs spanned by edges in each color are connected. This paper continues the study of connected Ramsey numbers, including the evaluation of several cases of trees versus complete graphs.

Matroid Generalizations Of Some Graph Results, Cameron Crenshaw

LSU Doctoral Dissertations

The edges of a graph have natural cyclic orderings. We investigate the matroids for which a similar cyclic ordering of the circuits is possible. A full characterization of the non-binary matroids with this property is given. Evidence of the difficulty of this problem for binary matroids is presented, along with a partial result for binary orderable matroids.

For a graph G, the ratio of |E(G)| to the minimum degree of G has a natural lower bound. For a matroid M that is representable over a finite field, we generalize this to a lower bound on …

Structure Of Extremal Unit Distance Graphs, Kaylee Weatherspoon

Senior Theses

This thesis begins with a selective overview of problems in geometric graph theory, a rapidly evolving subfield of discrete mathematics. We then narrow our focus to the study of unit-distance graphs, Euclidean coloring problems, rigidity theory and the interplay among these topics. After expounding on the limitations we face when attempting to characterize finite, separable edge-maximal unit-distance graphs, we engage an interesting Diophantine problem arising in this endeavor. Finally, we present a novel subclass of finite, separable edge-maximal unit distance graphs obtained as part of the author's undergraduate research experience.