Discrete Mathematics and Combinatorics Commons^™

Transformations On Double Occurrence Words Motivated By Dna Rearrangement, Daniel Cruz, Margherita Maria Ferrari, Lukas Nabergall, Natasa Jonoska, Masahico Saito

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

The Influence Of Canalization On The Robustness Of Finite Dynamical Systems, Claus Kadelka

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Combinatorial Geometry Of Threshold-Linear Networks, Christopher Langdon

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.

Reducing The Maximum Degree Of A Graph By Deleting Vertices: The Extremal Cases, Peter Borg, Kurt Fenech

Theory & Applications of Graphs

Let λ(G) denote the smallest number of vertices that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. In a recent paper, we proved that if n is the number of vertices of G,k is the maximum degree of G, and t is the number of vertices of degree k, then λ: (G) ≤ n+(k-1)t}{2k}. We also showed that λ (G) ≤ \frac{n}{k+1} if G is a tree. In this paper, we provide a new proof of the first bound and use it to determine the graphs that …

How Many Points Are There In A Line Segment? A New Answer From Discrete Cellular Space Viewpoint, Florentin Smarandache, Victor Christianto

Branch Mathematics and Statistics Faculty and Staff Publications

While it is known that Euclid’s five axioms include a proposition that a line consists at least of two points, modern geometry avoid consistently any discussion on the precise definition of point, line, etc. It is our aim to clarify one of notorious question in Euclidean geometry: how many points are there in a line segment? – from discrete-cellular space (DCS) viewpoint. In retrospect, it may offer an alternative of quantum gravity, i.e. by exploring discrete gravitational theories. To elucidate our propositions, in the last section we will discuss some implications of discrete cellular-space model in several areas of interest: …

Using Magic In Computing Education And Outreach, Ronald I. Greenberg, Dale F. Reed

Computer Science: Faculty Publications and Other Works

This special session explores the use of magic tricks based on computer science ideas; magic tricks help grab students' attention and can motivate them to invest more deeply in underlying CS concepts. Error detection ideas long used by computer scientists provide a particularly rich basis for working such "magic'', with a CS Unplugged parity check activity being a notable example. Prior work has shown that one can perform much more sophisticated tricks than the relatively well-known CS Unplugged activity, and these tricks can motivate analyses across a wide variety of computer science concepts and are relevant to learning objectives across …

Stranded Cellular Automaton And Weaving Products, Hao Yang

Mathematical Sciences Technical Reports (MSTR)

In order to analyze weaving products mathematically and find out valid weaving products, it is natural to relate them to Cellular Automaton. They are both generated based on specific rules and some initial conditions. Holden and Holden have created a Stranded Cellular Automaton that can represent common weaving and braiding products. Based on their previous findings, we were able to construct a Java program and analyze various aspects of the automaton they created. This paper will discuss the complexity of the Stranded Cellular Automaton, how to determine whether a weaving product holds together or not based on the automaton and …

Ideals, Big Varieties, And Dynamic Networks, Ian H. Dinwoodie

Mathematics and Statistics Faculty Publications and Presentations

The advantage of using algebraic geometry over enumeration for describing sets related to attractors in large dynamic networks from biology is advocated. Examples illustrate the gains.

Tutte-Equivalent Matroids, Maria Margarita Rocha

Electronic Theses, Projects, and Dissertations

We begin by introducing matroids in the context of finite collections of vectors from a vector space over a specified field, where the notion of independence is linear independence. Then we will introduce the concept of a matroid invariant. Specifically, we will look at the Tutte polynomial, which is a well-defined two-variable invariant that can be used to determine differences and similarities between a collection of given matroids. The Tutte polynomial can tell us certain properties of a given matroid (such as the number of bases, independent sets, etc.) without the need to manually solve for them. Although the Tutte …

Minimal Graphs With A Specified Code Map Image, Paul Feit

Theory & Applications of Graphs

Let G be a graph and ^e1,…^en be n distinct vertices. Let ρ be the metric on G. The code map on vertices, corresponding to this list, is c(x)=(ρ (x,^e1),…ρ (x,^en)). This paper introduces a variation: begin with V ⊆ Ζ^n for some n, and consider assignments of edges E such that the identity function on V is a code map for G=(V,E). Refer to such a set E as a code-match.

An earlier paper classified subsets of V for which at least one code-match exists. We prove …

Fractional Difference Operators And Related Boundary Value Problems, Scott C. Gensler

Department of Mathematics: Dissertations, Theses, and Student Research

In this dissertation we develop a fractional difference calculus for functions on a discrete domain. We start by showing that the Taylor monomials, which play a role analagous to that of the power functions in ordinary differential calculus, can be expressed in terms of a family of polynomials which I will refer to as the Pochhammer polynomials. These important functions, the Taylor monomials, were previously described by other scholars primarily in terms of the gamma function. With only this description it is challenging to understand their properties. Describing the Taylor monomials in terms of the Pochhammer polynomials has made it …

The Expected Number Of Patterns In A Random Generated Permutation On [N] = {1,2,...,N}, Evelyn Fokuoh

Electronic Theses and Dissertations

Previous work by Flaxman (2004) and Biers-Ariel et al. (2018) focused on the number of distinct words embedded in a string of words of length n. In this thesis, we will extend this work to permutations, focusing on the maximum number of distinct permutations contained in a permutation on [n] = {1,2,...,n} and on the expected number of distinct permutations contained in a random permutation on [n]. We further considered the problem where repetition of subsequences are as a result of the occurrence of (Type A and/or Type B) replications. Our method of enumerating the Type A replications causes double …

On The Strong Chromatic Index Of Sparse Graphs, Philip Deorsey, Jennifer Diemunsch, Michael Ferrara, Nathan Graber, Stephen Hartke, Sogol Jahanbekam, Bernard Lidicky, Luke Nelsen, Derrick Stolee, Eric Sullivan

Faculty Publications

The strong chromatic index of a graph G, denoted χ′s(G), is the least number of colors needed to edge-color G so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted χ′s,ℓ(G), is the least integer k such that if arbitrary lists of size k are assigned to each edge then G can be edge-colored from those lists where edges at distance at most two receive distinct colors.We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if G is a subcubic planar graph with girth(G)≥41 then χ′s,ℓ(G)≤5, answering a question …

Circulant Matrices And Mathematical Juggling, Richard A. Brualdi, Michael W. Schroeder

Mathematics Faculty Research

Circulants form a well-studied and important class of matrices, and they arise in many algebraic and combinatorial contexts, in particular as multiplication tables of cyclic groups and as special classes of latin squares. There is also a known connection between circulants and mathematical juggling. The purpose of this note is to expound on this connection developing further some of its properties. We also formulate some problems and conjectures with some computational data supporting them.

Integer-Antimagic Spectra Of Disjoint Unions Of Cycles, Wai Chee Shiu

Theory & Applications of Graphs

Let A be a non-trivial abelian group. A simple graph G = (V, E) is A-antimagic if there exists an edge labeling f: E(G) \to A \setminus \{0\} such that the induced vertex labeling f^+: V(G) \to A, defined by f^+(v) = \sum_{uv\in E(G)}f(uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = \{k\;|\; G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}. In this paper, we determine the integer-antimagic spectra of disjoint unions of cycles.

An Efficient Algorithm To Test Forcibly-Connectedness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

We present an algorithm to test whether a given graphical degree sequence is forcibly connected or not and prove its correctness. We also outline the extensions of the algorithm to test whether a given graphical degree sequence is forcibly k-connected or not for every fixed k ≥ 2. We show through experimental evaluations that the algorithm is efficient on average, though its worst case run time is probably exponential. We also adapt Ruskey et al's classic algorithm to enumerate zero-free graphical degree sequences of length n and Barnes and Savage's classic algorithm to enumerate graphical partitions of even integer …

Finite Asymptotic Clusters Of Metric Spaces, Viktoriia Bilet, Oleksiy Dovgoshey

Theory & Applications of Graphs

Let (X, d) be an unbounded metric space and let \tilde r=(r_n)_{n\in\mathbb N} be a sequence of positive real numbers tending to infinity. A pretangent space \Omega_{\infty, \tilde r}^{X} to (X, d) at infinity is a limit of the rescaling sequence \left(X, \frac{1}{r_n}d\right). The set of all pretangent spaces \Omega_{\infty, \tilde r}^{X} is called an asymptotic cluster of pretangent spaces. Such a cluster can be considered as a weighted graph (G_{X, \tilde r}, \rho_{X}) whose maximal cliques coincide with \Omega_{\infty, \tilde r}^{X} and the weight \rho_{X} is defined by metrics on \Omega_{\infty, \tilde r}^{X}. We describe the structure …

A Computer-Aided Decomposition Of The Complete Digraph Into Orientations Of K4 − E With A Double Edge, Hanson Hao

The International Student Science Fair 2018

The abstract is available as an Additional File.

A Computer-Aided Decomposition Of The Complete Digraph Into Orientations Of K4 − E With A Double Edge, Hanson Hao '19, Claudia Zhu '18

Student Publications & Research

The abstract is available as an Additional File.

Unavoidable Immersions And Intertwines Of Graphs, Matthew Christopher Barnes

LSU Doctoral Dissertations

The topological minor and the minor relations are well-studied binary relations on the class of graphs. A natural weakening of the topological minor relation is an immersion. An immersion of a graph H into a graph G is a map that injects the vertex set of H into the vertex set of G such that edges between vertices of H are represented by pairwise-edge-disjoint paths of G. In this dissertation, we present two results: the first giving a set of unavoidable immersions of large 3-edge-connected graphs and the second on immersion intertwines of infinite graphs. These results, along with …

Dimers On Cylinders Over Dynkin Diagrams And Cluster Algebras, Maitreyee Chandramohan Kulkarni

LSU Doctoral Dissertations

This dissertation describes a general setting for dimer models on cylinders over Dynkin diagrams which in type A reduces to the well-studied case of dimer models on a disc. We prove that all Berenstein--Fomin--Zelevinsky quivers for Schubert cells in a symmetric Kac--Moody algebra give rise to dimer models on the cylinder over the corresponding Dynkin diagram. We also give an independent proof of a result of Buan, Iyama, Reiten and Smith that the corresponding superpotentials are rigid using the dimer model structure of the quivers.

Templates For Representable Matroids, Kevin Manuel Grace

LSU Doctoral Dissertations

The matroid structure theory of Geelen, Gerards, and Whittle has led to a hypothesis that a highly connected member of a minor-closed class of matroids representable over a finite field is a mild modification (known as a perturbation) of a frame matroid, the dual of a frame matroid, or a matroid representable over a proper subfield. They introduced the notion of a template to describe these perturbations in more detail. In this dissertation, we determine these templates for various classes and use them to prove results about representability, extremal functions, and excluded minors.

Chapter 1 gives a brief introduction …

Two Results In Drawing Graphs On Surfaces, Joshua E. Fallon

LSU Doctoral Dissertations

In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct 2-crossing-critical graphs for each non-orientable surface. Next, we use 2-amalgamations to construct 2-crossing-critical graphs for each orientable surface other than the sphere. Finally, we contribute to the pursuit of characterizing 4-connected graphs that embed on the Klein bottle and fail to be edge-hamiltonian. We show that known 4-connected counterexamples to edge-hamiltonicity on the Klein bottle are hamiltonian …

Gamma-Realizability And Other Musings On Inverse Domination, John Asplund, Joe Chaffee, James M. Hammer Iii, Matt Noble

Theory & Applications of Graphs

We introduce and study γ-realizable sequences. For a finite, simple graph G containing no isolated vertices, I ⊆ V(G) is said to be an inverse dominating set if I dominates all of G and I is contained by the complement of some minimum dominating set D. Define a sequence of positive integers (x₁,…, x_n) to be γ-realizable if there exists a graph G having exactly n distinct minimum dominating sets D₁,… D_n where for each i ∈ {1,… n}, the minimum size of an inverse dominating set in V(G) …

Incomplete Generalized (P; Q; R)-Tribonacci Polynomials, Mark Shattuck, Elif Tan

Applications and Applied Mathematics: An International Journal (AAM)

In this paper, we consider an extension of the tribonacci polynomial, which we will refer to as the generalized (p; q; r)-tribonacci polynomial, denoted by T_n;m(x).We find an explicit formula for T_n;m(x)which we use to introduce the incomplete generalized (p; q; r)-tribonacci polynomials and derive several properties. An explicit formula for the generating function of the incomplete generalized polynomials is determined and a combinatorial interpretation is provided yielding further identities.

On B-Chromatic Number Of Prism Graph Families, Nadeem Ansari, R. S. Chandel, Rizwana Jamal

Applications and Applied Mathematics: An International Journal (AAM)

A b-coloring of graph 𝐺 is a proper 𝑘-coloring 𝐶 that verifies the following property: for every color class 𝑐𝑖, 1≤𝑖≤𝑘, there exists a vertex 𝑥𝑖, with color 𝑐𝑖, such that all the other colors in 𝐶 are utilized in 𝑥𝑖 neighbors. The b-chromatic number of a graph 𝐺, denoted by 𝜑(𝐺), is the largest integer 𝑘 such that 𝐺 may have a b-coloring by 𝑘 colors. In this paper we discuss the b-coloring of prism graph 𝑌𝑛, central graph of prism graph 𝐶(𝑌𝑛), middle graph of prism graph 𝑀(𝑌𝑛) and the total graph of prism graph 𝑇(𝑌𝑛) and we …

Distance Product Of Graphs, H. S. Mehta, U. P. Acharya

Applications and Applied Mathematics: An International Journal (AAM)

In graph theory, different types of product of two graphs have been studied, e.g. Cartesian product, Tensor product, Strong product, etc. Later on, Cartesian product and Tensor product have been generalized by 2-Cartesian product and 2-Tensor product. In this paper, we give one more generalize form, distance product of two graphs. Mainly we discuss the connectedness, bipartiteness and Eulerian property in this product.

The Search For The Cyclic Sieving Phenomenon In Plane Partitions, William J. Asztalos

DePaul Discoveries

The efforts of this research project are best understood in the context of the subfield of dynamical combinatorics, in which one enumerates a set of combinatorial objects by defining some action to guide the search for underlying structures. While there are many examples with varying degrees of complexity, the necklace problem, which concerns the possible unique configurations of beads in a ring up to rotational symmetry, is a well-known example. Though this sort of approach to enumeration has been around for a century or more, activity in this area has intensified in the last couple of decades. Perhaps the most …

Additive List Coloring Of Planar Graphs With Given Girth, Axel Brandt, Sogol Jahanbekam, Jennifer Diemunsch

Faculty Publications

An additive coloring of a graph G is a labeling of the vertices of G from {1,2,...,k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted \luck(G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and …

Golden Arm: A Probabilistic Study Of Dice Control In Craps, Donald R. Smith, Robert Scott Iii

UNLV Gaming Research & Review Journal

This paper calculates how much control a craps shooter must possess on dice outcomes to eliminate the house advantage. A golden arm is someone who has dice control (or a rhythm roller or dice influencer). There are various strategies for dice control in craps. We discuss several possibilities of dice control that would result in several different mathematical models of control. We do not assert whether dice control is possible or not (there is a lack of published evidence). However, after studying casino-legal methods described by dice-control advocates, we can see only one realistic mathematical model that describes the resulting …