Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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 …

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.

Optimal Orientations Of Vertex-Multiplications Of Trees With Diameter 4, Willie Han Wah Wong, Eng Guan Tay

Theory and Applications of Graphs

\noindent Koh and Tay proved a fundamental classification of $G$ vertex-multiplications into three classes $\mathscr{C}_0, \mathscr{C}_1$ and $\mathscr{C}_2$. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class $\mathscr{C}_2$. Of interest, $G$ vertex-multiplications are extensions of complete $n$-partite graphs and Gutin characterised complete bipartite graphs with orientation number 3 (or 4 resp.) via an ingenious use of Sperner's theorem. In this paper, we investigate vertex-multiplications of trees with diameter $4$ in $\mathscr{C}_0$ (or $\mathscr{C}_1$) and exhibit its intricate connections with problems in Sperner Theory, thereby extending Gutin's approach. Let $s$ …

The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison

Rose-Hulman Undergraduate Mathematics Journal

A graph $G$ is said to be \emph{d-distinguishable} if there exists a not-necessarily proper coloring with $d$ colors such that only the trivial automorphism preserves the color classes. For a 2-distinguishing labeling, the \emph{ cost of $2$-distinguishing}, denoted $\rho(G),$ is defined as the minimum size of a color class over all $2$-distinguishing colorings of $G$. Our work also utilizes \emph{determining sets} of $G, $ sets of vertices $S \subseteq G$ such that every automorphism of $G$ is uniquely determined by its action on $S.$ The \emph{determining number} of a graph is the size of a smallest determining set. We investigate …

Iterated Jump Graphs, Fran Herr, Legrand Jones Ii

Rose-Hulman Undergraduate Mathematics Journal

The jump graph J(G) of a simple graph G has vertices which represent edges in G where two vertices in J(G) are adjacent if and only if the corresponding edges in G do not share an endpoint. In this paper, we examine sequences of graphs generated by iterating the jump graph operation and characterize the behavior of this sequence for all initial graphs. We build on work by Chartrand et al. who showed that a handful of jump graph sequences terminate and two sequences converge. We extend these results by showing that there are no non-trivial repeating sequences of jump …

The Chromatic Index Of Ring Graphs, Lilian Shaffer

Rose-Hulman Undergraduate Mathematics Journal

The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or …

Outer Independent Double Italian Domination Of Some Graph Products, Rouhollah Jalaei, Doost Ali Mojdeh

Theory and Applications of Graphs

An outer independent double Italian dominating function on a graph $G$ is a function $f:V(G)\rightarrow\{0,1,2,3\}$ for which each vertex $x\in V(G)$ with $\color{red}{f(x)\in \{0,1\}}$ then $\sum_{y\in N[x]}f(y)\geqslant 3$ and vertices assigned $0$ under $f$ are independent. The outer independent double Italian domination number $\gamma_{oidI}(G)$ is the minimum weight of an outer independent double Italian dominating function of graph $G$. In this work, we present some contributions to the study of outer independent double Italian domination of three graph products. We characterize the Cartesian product, lexicographic product and direct product of custom graphs in terms of this parameter. We also provide …