Discrete Mathematics and Combinatorics Commons^™

On Saturation Numbers Of Ramsey-Minimal Graphs, Hunter M. Davenport

Honors Undergraduate Theses

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H₁,...,H_k) if every k-edge-coloring of G contains a monochromatic copy of H_i in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K₃or blue K …

Polytopes Associated To Graph Laplacians, Marie Meyer

Theses and Dissertations--Mathematics

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, P_G, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, P_D.

Basic properties of both families of simplices, P_G and P …

On The Density Of The Odd Values Of The Partition Function, Samuel Judge

Dissertations, Master's Theses and Master's Reports

The purpose of this dissertation is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely the conjecture that the partition function $p(n)$ is equidistributed modulo $2$. We provide a doubly-indexed, infinite family of conjectural identities in the ring of series $\Z_2[[q]]$, which relate $p(n)$ with suitable $t$-multipartition functions, and show how to, in principle, prove each such identity. We will exhibit explicit proofs for $32$ of our identities. However, the conjecture remains open in full generality. A striking consequence of these conjectural identities is that, under suitable …

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …

Sparse Trees With A Given Degree Sequence, Ao Shen

College of Graduate Studies: Theses & Dissertations

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k�� Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k�� Wiener index of a tree T is …

String C-Groups Of Order 1024, Yasushi Gomi, Mark L. Loyola, Ma. Louise Antonette N. De Las Peñas

Mathematics Faculty Publications

This paper determines the nondegenerate string C-groups of order 1024. For groups of rank 3, we use the technique of central extension of string C-groups of order 512. For groups of rank at least 4, we compute for quotients of universal string C-groups.

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory & Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of …

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory & Applications of Graphs

Given a graph H and a positive integer k, the k-color Gallai-Ramsey number gr_k(K3 : H) is defined to be the minimum number of vertices n for which any k-coloring of the complete graph K_n contains either a rainbow triangle or a monochromatic copy of H. The behavior of these numbers is rather well understood when H is bipartite but when H is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs H to a value that we conjecture to …

On The Planarity Of Generalized Line Graphs, Khawlah H. Alhulwah, Mohra Zayed, Ping Zhang

Theory & Applications of Graphs

One of the most familiar derived graphs is the line graph. The line graph L(G) of a graph G is that graph whose vertices are the edges of G where two vertices of L(G) are adjacent if the corresponding edges are adjacent in G. Two nontrivial paths P and Q in a graph G are said to be adjacent paths in G if P and Q have exactly one vertex in common and this vertex is an end-vertex of both P and Q. For an integer ℓ ≥ 2, the ℓ -line graph Lℓ (G) of a …

Pbw Bases And Marginally Large Tableaux In Type D, Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

We give an explicit description of the unique crystal isomorphism between two realizations of B(∞) in type D: that using marginally large tableaux and that using PBW monomials with respect to one particularly nice reduced expression of the longest word

Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins

Murray State Theses and Dissertations

We present two families of diamond-colored distributive lattices – one known and one new – that we can show are models of the type C one-rowed Weyl symmetric functions. These lattices are constructed using certain sequences of positive integers that are visualized as filling the boxes of one-rowed partition diagrams. We show how natural orderings of these one-rowed tableaux produce our distributive lattices as sublattices of a more general object, and how a natural coloring of the edges of the associated order diagrams yields a certain diamond-coloring property. We show that each edge-colored lattice possesses a certain structure that is …

On The Domination Chain Of M By N Chess Graphs, Kathleen Johnson

Murray State Theses and Dissertations

A survey of the six domination chain parameters for both square and rectangular chess boards are discussed.

Characterizations Of Some Classes Of Graphs That Are Nearly Series-Parallel, Victoria Fontaine

LSU Doctoral Dissertations

A series-parallel graph can be built from a single-edge graph by a sequence of series and parallel extensions. The class of such graphs coincides with the class of graphs that do not have the complete graph K₄ as a minor. This dissertation considers a class M₁ of graphs that are close to being series-parallel. In particular, every member of the class has the property that one can obtain a series-parallel graph by adding a new edge and contracting it out, or by splitting a vertex into two vertices whose neighbor sets partition the neighbor set of the original …

An Exploration Of The Chromatic Polynomial, Amanda Aydelotte

Mathematics Undergraduate Theses

In 1912, George Birkhoff was studying the Four Color Problem, and in doing so introduced the concept of the chromatic polynomial. While this did not end up directly contributing to proving that every map could be colored with four colors such that no region shares a border with another region of the same color, the chromatic polynomial has been found to have some very interesting properties. In this paper, it will be our goal to examine some of these properties and use them to determine information about their corresponding graphs.

Optimal Layout For A Component Grid, Michael W. Ebert

Computer Science and Software Engineering

Several puzzle games include a specific type of optimization problem: given components that produce and consume different resources and a grid of squares, find the optimal way to place the components to maximize output. I developed a method to evaluate potential solutions quickly and automated the solving of the problem using a genetic algorithm.

Classification Of Minimal Separating Sets In Low Genus Surfaces, J. J. P. Veerman, William Maxwell, Victor Rielly, Austin K. Williams

Mathematics and Statistics Faculty Publications and Presentations

Consider a surface S and let M ⊂ S. If S \ M is not connected, then we say M separates S, and we refer to M as a separating set of S. If M separates S, and no proper subset of M separates S, then we say M is a minimal separating set of S. In this paper we use computational methods of combinatorial topology to classify the minimal separating sets of the orientable surfaces of genus g = 2 and g = 3. The classification for genus 0 and 1 was done …

Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens

Theory & Applications of Graphs

It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of K_n with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently …

A High Quality, Eulerian 3d Fluid Solver In C++, Lejon Anthony Mcgowan

Computer Science and Software Engineering

Fluids are a part of everyday life, yet are one of the hardest elements to properly render in computer graphics. Water is the most obvious entity when thinking of what a fluid simulation can achieve (and it is indeed the focus of this project), but many other aspects of nature, like fog, clouds, and particle effects. Real-time graphics like video games employ many heuristics to approximate these effects, but large-scale renderers aim to simulate these effects as closely as possible.

In this project, I wish to achieve effects of the latter nature. Using the Eulerian technique of discrete grids, I …

Graph Structures In Bipolar Neutrosophic Environment, Florentin Smarandache, Muhammad Akram, Muzzamal Sitara

Branch Mathematics and Statistics Faculty and Staff Publications

A bipolar single-valued neutrosophic (BSVN) graph structure is a generalization of a bipolar fuzzy graph. In this research paper, we present certain concepts of BSVN graph structures. We describe some operations on BSVN graph structures and elaborate on these with examples. Moreover, we investigate some related properties of these operations.

An Extended Formulation Of The Convex Recoloring Problem On A Phylogenetic Tree, Sangho Shim

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.