Discrete Mathematics and Combinatorics Commons^™

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 …

The Average Measure Of A K-Dimensional Simplex In An N-Cube, John A. Carter

Graduate Theses/Dissertations

Within an n-dimensional unit cube, a number of k-dimensional simplices can be formed whose vertices are the vertices of the n-cube. In this thesis, we analyze the average measure of a k-simplex in the n-cube. We develop exact equations for the average measure when k = 1, 2, and 3. Then we generate data for these cases and conjecture that their averages appear to approach n^k/2 times some constant. Using the convergence of Bernstein polynomials and a k-simplex Bernstein generalization, we prove the conjecture is true for the 1-simplex and 2-simplex cases. We then develop a generalized formula for …

Secure Multiparty Protocol For Differentially-Private Data Release, Anthony Harris

Boise State University Theses and Dissertations

In the era where big data is the new norm, a higher emphasis has been placed on models which guarantees the release and exchange of data. The need for privacy-preserving data arose as more sophisticated data-mining techniques led to breaches of sensitive information. In this thesis, we present a secure multiparty protocol for the purpose of integrating multiple datasets simultaneously such that the contents of each dataset is not revealed to any of the data owners, and the contents of the integrated data do not compromise individual’s privacy. We utilize privacy by simulation to prove that the protocol is privacy-preserving, …

Graphs With Few Spanning Substructures, Jessica De Silva

Department of Mathematics: Dissertations, Theses, and Student Research

In this thesis, we investigate a number of problems related to spanning substructures of graphs. The first few chapters consider extremal problems related to the number of forest-like structures of a graph. We prove that one can find a threshold graph which contains the minimum number of spanning pseudoforests, as well as rooted spanning forests, amongst all graphs on n vertices and e edges. This has left the open question of exactly which threshold graphs have the minimum number of these spanning substructures. We make progress towards this question in particular cases of spanning pseudoforests.

The final chapter takes on …

On Coding For Partial Erasure Channels, Carolyn Mayer

Department of Mathematics: Dissertations, Theses, and Student Research

Error correcting codes have been essential to the technology we use in everyday life in digital storage, wireless communication, barcodes, and much more. Different channel models are used for different types of communication (for example, if information is sent to one person or to many people) and different types of errors. Partial erasure channels were recently introduced to model applications in which some information remains after an erasure event. These remnants of information may be used to increase the chances of successful decoding. We introduce a new partial erasure channel in which partial erasures correspond to individual bit erasures in …

Vector Partitions, Jennifer French

Electronic Theses and Dissertations

Integer partitions have been studied by many mathematicians over hundreds of years. Many identities exist between integer partitions, such as Euler’s discovery that every number has the same amount of partitions into distinct parts as into odd parts. These identities can be proven using methods such as conjugation or generating functions. Over the years, mathematicians have worked to expand partition identities to vectors. In 1963, M. S. Cheema proved that every vector has the same number of partitions into distinct vectors as into vectors with at least one component odd. This parallels Euler’s result for integer partitions. The primary purpose …

Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole

Undergraduate Honors Theses

Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the d^t t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds …

On Some Geometry Of Graphs, Zachary S. Mcguirk

Dissertations, Theses, and Capstone Projects

In this thesis we study the intrinsic geometry of graphs via the constants that appear in discretized partial differential equations associated to those graphs. By studying the behavior of a discretized version of Bochner's inequality for smooth manifolds at the cone point for a cone over the set of vertices of a graph, a lower bound for the internal energy of the underlying graph is obtained. This gives a new lower bound for the size of the first non-trivial eigenvalue of the graph Laplacian in terms of the curvature constant that appears at the cone point and the size of …

An Optimized Route For Q100'S Bert And Kristin To Visit All Jersey Mike's Subs In Atlanta For Charity

Symposium of Student Scholars

The Bert Show is a popular morning show on Atlanta’s Q100 radio station. They host a non-profit organization that provides a “magical, all-expenses-paid, five-day journey to Walt Disney World for children with chronic and terminal illnesses and their families” called “Bert’s Big Adventure.” On March 28^th, 2018, thirty-seven locations of Jersey Mike’s are participating in the their Jersey Mike’s Day of Giving to support Bert’s Big Adventure. The goal is to have two popular radio show hosts visit each of these locations for some photos and presence to draw in more customers! But how do we get two …

Efficient Reduced Bias Genetic Algorithm For Generic Community Detection Objectives, Aditya Karnam Gururaj Rao

Theses

The problem of community structure identification has been an extensively investigated area for biology, physics, social sciences, and computer science in recent years for studying the properties of networks representing complex relationships. Most traditional methods, such as K-means and hierarchical clustering, are based on the assumption that communities have spherical configurations. Lately, Genetic Algorithms (GA) are being utilized for efficient community detection without imposing sphericity. GAs are machine learning methods which mimic natural selection and scale with the complexity of the network. However, traditional GA approaches employ a representation method that dramatically increases the solution space to be searched by …

On Structures Of Large Rooted Graphs, Shilin Wang

LSU Doctoral Dissertations

A rooted graph is a pair (G,R), where G is a graph and R⊆V(G). There are two research topics in this thesis. One is about unavoidable substructures in sufficiently large rooted graphs. The other is about characterizations of rooted graphs excluding specific large graphs.

The first topic of this thesis is motivated by Ramsey Theorem, which states that K_n and ¯(K_n ) are unavoidable induced subgraphs in every sufficiently large graph. It is also motivated by a classical result of Oporowski, Oxley, and Thomas, which determines unavoidable large 3-connected minors. We first determine unavoidable induced subgraphs, and unavoidable subgraphs in …

Vertex-Relaxed Graceful Labelings Of Graphs And Congruences, Florin Aftene

Masters Theses & Specialist Projects

A labeling of a graph is an assignment of a natural number to each vertex

of a graph. Graceful labelings are very important types of labelings. The study of graceful labelings is very difficult and little has been shown about such labelings. Vertex-relaxed graceful labelings of graphs are a class of labelings that include graceful labelings, and their study gives an approach to the study of graceful labelings. In this thesis we generalize the congruence approach of Rosa to obtain new criteria for vertex-relaxed graceful labelings of graphs. To do this, we generalize Faulhaber’s Formula, which is a famous result …