The Traveling Salesman Problem At Taylor University,
2023
Taylor University
The Traveling Salesman Problem At Taylor University, Jonathan Jinoo Pawley
Mathematics Student Projects
What is the shortest route to walk to every residence hall on campus, beginning and ending with the same hall? This question can be considered by applying the Traveling Salesman Problem, an easy to understand yet hard to solve problem in the realm of discrete combinatorial optimization. The Traveling Salesman Problem is useful as an introduction to optimization problems, and it also has immensely practical applications. This paper will serve as an introduction to the computational difficulty of the Traveling Salesman Problem and will also explore various approximation algorithms. We will subsequently apply our new understanding of the theory to …
K-Distinct Lattice Paths,
2023
Valparaiso University
K-Distinct Lattice Paths, Eric J. Yager, Marcus Engstrom
Rose-Hulman Undergraduate Mathematics Journal
Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of k-distinct paths is of general interest. We extend the work previously done by Gillman et. al. to determine the order of a maximum set of k-distinct lattice paths. In particular, we disprove a conjecture by Gillman that a greedy algorithm gives this maximum order and also refine an upper bound given by Brewer et. al. We illustrate that brute force is an inefficient method to determine the maximum order, as it has time complexity O(nk).
Utilizing Graph Thickness Heuristics On The Earth-Moon Problem,
2023
York College of Pennsylvania
Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver
Rose-Hulman Undergraduate Mathematics Journal
This paper utilizes heuristic algorithms for determining graph thickness in order to attempt to find a 10-chromatic thickness-2 graph. Doing so would eliminate 9 colors as a potential solution to the Earth-moon Problem. An empirical analysis of the algorithms made by the author are provided. Additionally, the paper lists various graphs that may or nearly have a thickness of 2, which may be solutions if one can find two planar subgraphs that partition all of the graph’s edges.
On Nowhere Zero 4-Flows In Regular Matroids,
2023
Indiana University Northwest
On Nowhere Zero 4-Flows In Regular Matroids, Xiaofeng Wang, Taoye Zhang, Ju Zhou
Theory & Applications of Graphs
Walton and Welsh proved that if a co-loopless regular matroid M does not have a minor in {M(K(3,3)),M∗(K5)}, then M admits a nowhere zero 4-flow. Lai, Li and Poon proved that if M does not have a minor in {M(K5),M∗(K5)}, then M admits a nowhere zero 4-flow. We prove that if a co-loopless regular matroid M does not have a minor in {M((P10)¯3 ),M∗(K5)}, then M admits a nowhere zero 4-flow where (P10)¯3 is the graph obtained from the Petersen graph P10by contracting 3 edges of a perfect matching. As …
The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$,
2023
University of Notre Dame
The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales
Rose-Hulman Undergraduate Mathematics Journal
DNA and other polymer chains in confined spaces behave like closed loops. Arsuaga et al. \cite{AB} introduced the uniform random polygon model in order to better understand such loops in confined spaces using probabilistic and knot theoretical techniques, giving some classification on the mean squared linking number of such loops. Flapan and Kozai \cite{flapan2016linking} extended these techniques to find the mean sum of squared linking numbers for random linear embeddings of complete graphs $K_n$ and found it to have order $\Theta(n(n!))$. We further these ideas by inspecting random piecewise-linear embeddings of complete graphs and give introductory-level summaries of the ideas …
Reversibility Of Stranded Cellular Automata,
2023
Rose-Hulman Institute of Technology
Reversibility Of Stranded Cellular Automata, Allyn Loyd
Mathematical Sciences Technical Reports (MSTR)
Cellular automata, such as the Stranded Cellular Automaton (SCA) model created by Joshua and Lana Holden, can be used to model weaving patterns. Similar models can be constructed to model macrame patterns, where strands are knotted together. If a rule is injective, then it is reversible. If a rule is surjective, then every configuration has at least one predecessor. In this paper, we will discuss the injectivity and surjectivity of several new SCA models in order to find reversible rules. We will also analyze the number of configurations with no predecessors and the number of configurations that map to the …
On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms,
2023
CUNY Graduate Center
On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms, Yin Choi Cheng
Dissertations, Theses, and Capstone Projects
This work consists of two parts. In the first part, we study the order-type complexity of right-infinite words over a finite alphabet, which is defined to be the order types of the set of shifts of said words in lexicographical order. The set of shifts of any aperiodic morphic words whose first letter in the purely-morphic pre-image occurs at least twice in the pre-image has the same order type as Q ∩ (0, 1), Q ∩ (0, 1], or Q ∩ [0, 1). This includes all aperiodic purely-morphic binary words. The order types of uniform-morphic ternary words were also studied, …
Fuglede's Conjecture In Some Finite Abelian Groups,
2023
CUNY Graduate Center
Fuglede's Conjecture In Some Finite Abelian Groups, Thomas Fallon
Dissertations, Theses, and Capstone Projects
This dissertation thoroughly examines Fuglede's Conjecture within some discrete settings, shedding light on its intricate details. Fuglede's Conjecture establishes a profound connection between the geometric property of being a tiling set and the analytical attribute of being a spectral set. By exploring the conjecture on various discrete settings, this thesis delves into the implications and ramifications of the conjecture, unraveling its implications within the field.
Evaluation Of Symmetric Functions And Boolean Functions Over Stochastic Input,
2023
CUNY Graduate Center
Evaluation Of Symmetric Functions And Boolean Functions Over Stochastic Input, Naifeng Liu
Dissertations, Theses, and Capstone Projects
In our daily life, we often face situations where we need to make precise judgments based on initially unknown information, while gathering all the evidence to make informed conclusions can be very costly. In this dissertation, we explore the problem of optimizing the decision-making process under uncertainty, and we focus on problems that can be found in both theoretical computer science and discrete mathematics. The primary goal is to develop approximation algorithms with guaranteed worst-case performance. These algorithms aim to minimize the expected cost of acquiring information necessary for evaluating fundamental functions, such as Boolean and symmetric functions. Furthermore, we …
An Analysis Of The Sequence Xn+2 = I M Xn+1 + Xn,
2023
Coastal Carolina University
An Analysis Of The Sequence Xn+2 = I M Xn+1 + Xn, David Duncan, Prashant Sansgiry, Ogul Arslan, Jensen Meade
Journal of the South Carolina Academy of Science
We analyze the sequence Xn+2 = imXn+1 + Xn, with X1 = X2 = 1 + i, where i is the imaginary number and m is a real number. Plotting the sequence in the complex plane for different values of m, we see interesting figures from the conic sections. For values of m in the interval (−2, 2) we show that the figures generated are ellipses. We also provide analysis which prove that for certain values of m, the sequence generated is periodic with even period.
The Gamma-Signless Laplacian Adjacency Matrix Of Mixed Graphs,
2023
College of Engineering and Technology, American University of the Middle East, Kuwait
The Gamma-Signless Laplacian Adjacency Matrix Of Mixed Graphs, Omar Alomari, Mohammad Abudayah, Manal Ghanem
Theory & Applications of Graphs
The α-Hermitian adjacency matrix Hα of a mixed graph X has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number α. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the gamma-signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of …
Signings Of Graphs And Sign-Symmetric Signed Graphs,
2023
Mississippi State University
Signings Of Graphs And Sign-Symmetric Signed Graphs, Ahmad Asiri
Theses and Dissertations
In this dissertation, we investigate various aspects of signed graphs, with a particular focus on signings and sign-symmetric signed graphs. We begin by examining the complete graph on six vertices with one edge deleted ($K_6$\textbackslash e) and explore the different ways of signing this graph up to switching isomorphism. We determine the frustration index (number) of these signings and investigate the existence of sign-symmetric signed graphs. We then extend our study to the $K_6$\textbackslash 2e graph and the McGee graph with exactly two negative edges. We investigate the distinct ways of signing these graphs up to switching isomorphism and demonstrate …
A Machine Learning Approach To Constructing Ramsey Graphs Leads To The Trahtenbrot-Zykov Problem.,
2023
University of Louisville
A Machine Learning Approach To Constructing Ramsey Graphs Leads To The Trahtenbrot-Zykov Problem., Emily Hawboldt
Electronic Theses and Dissertations
Attempts at approaching the well-known and difficult problem of constructing Ramsey graphs via machine learning lead to another difficult problem posed by Zykov in 1963 (now commonly referred to as the Trahtenbrot-Zykov problem): For which graphs F does there exist some graph G such that the neighborhood of every vertex in G induces a subgraph isomorphic to F? Chapter 1 provides a brief introduction to graph theory. Chapter 2 introduces Ramsey theory for graphs. Chapter 3 details a reinforcement learning implementation for Ramsey graph construction. The implementation is based on board game software, specifically the AlphaZero program and its …
Dna Self-Assembly Of Trapezohedral Graphs,
2023
California State University - San Bernardino
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 …
One Formula For Non-Prime Numbers: Motivations And Characteristics,
2023
Department of Basic Science, Faculty of Engineering, The British University in Egypt
One Formula For Non-Prime Numbers: Motivations And Characteristics, Mahmoud Mansour, Kamal Hassan Prof.
Basic Science Engineering
Primes are essential for computer encryption and cryptography, as they are fundamental units of whole numbers and are of the highest importance due to their mathematical qualities. However, identifying a pattern of primes is not easy. Thinking in a different way may get benefits, by considering the opposite side of the problem which means focusing on non-prime numbers. Recently, researchers introduced, the pattern of non-primes in two maximal sets while in this paper, non-primes are presented in one formula. Getting one-way formula for non-primes may pave the way for further applications based on the idea of primes.
Incidence And Laplacian Matrices Of Wheel Graphs And Their Inverses,
2023
Marshall University
Incidence And Laplacian Matrices Of Wheel Graphs And Their Inverses, Jerad Ipsen, Sudipta Mallik
Mathematics Faculty Research
It has been an open problem to find the Moore-Penrose inverses of the incidence, Laplacian, and signless Laplacian matrices of families of graphs except trees and unicyclic graphs. Since the inverse formulas for an odd unicyclic graph and an even unicyclic graph are quite different, we consider wheel graphs as they are formed from odd or even cycles. In this article we solve the open problem for wheel graphs. This work has an interesting connection to inverses of circulant matrices.
Waste Treatment Facility Location For Hotel Chains,
2023
Universidad de Las Palmas de Gran Canaria
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,
2023
Universidad Nacional Autónoma de México
A Bit-Parallel Tabu Search Algorithm For Finding Es2 -Optimal And Minimax-Optimal Supersaturated Designs, Luis B. Morales, Dursun A. Bulutoglu
Faculty Publications
We prove the equivalence of two-symbol supersaturated designs (SSDs) with N (even) rows, m columns, smax=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(s2)-optimal and minimax-optimal SSDs with smax ∈ {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(s2)-optimal and minimax-optimal SSDs achieving the sharpest known E(s2) lower bound with …
A Pebbling Game On Powers Of Paths,
2023
Lehigh University
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 …
Discrete Polylogarithm Functions,
2023
Marshall University
Discrete Polylogarithm Functions, Tom Cuchta, Dallas Freeman
Mathematics Faculty Research
We investigate a discrete analogue of the polylogarithm function. Difference and summation relations are obtained, as well as its connection to the discrete hypergeometric series.
