Discrete Mathematics and Combinatorics Commons^™

Δ-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 …

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 …

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 …

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 …

A Stronger Strong Schottky Lemma For Euclidean Buildings, Michael E. Ferguson

Dissertations, Theses, and Capstone Projects

We provide a criterion for two hyperbolic isometries of a Euclidean building to generate a free group of rank two. In particular, we extend the application of a Strong Schottky Lemma to buildings given by Alperin, Farb and Noskov. We then use this extension to obtain an infinite family of matrices that generate a free group of rank two. In doing so, we also introduce an algorithm that terminates in finite time if the lemma is applicable for pairs of certain kinds of matrices acting on the Euclidean building for the special linear group over certain discretely valued fields.

Counting Power Domination Sets In Complete M-Ary Trees, Hays Whitlatch, Katharine Shultis, Olivia Ramirez, Michele Ortiz, Sviatlana Kniahnitskaya

Theory and Applications of Graphs

Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this paper we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time.

Hs-Integral And Eisenstein Integral Mixed Circulant Graphs, Monu Kadyan, Bikash Bhattacharjya

Theory and Applications of Graphs

A mixed graph is called \emph{second kind hermitian integral} (\emph{HS-integral}) if the eigenvalues of its Hermitian-adjacency matrix of the second kind are integers. A mixed graph is called \emph{Eisenstein integral} if the eigenvalues of its (0, 1)-adjacency matrix are Eisenstein integers. We characterize the set $S$ for which a mixed circulant graph $\text{Circ}(\mathbb{Z}_n, S)$ is HS-integral. We also show that a mixed circulant graph is Eisenstein integral if and only if it is HS-integral. Further, we express the eigenvalues and the HS-eigenvalues of unitary oriented circulant graphs in terms of generalized M$\ddot{\text{o}}$bius function.

Strong Homotopy Lie Algebras And Hypergraphs, Samuel J. Bevins, Marco Aldi

Undergraduate Research Posters

We study hypergraphs by attaching a nilpotent strong homotopy Lie algebra. We especially focus on hypergraph theoretic information that is encoded in the cohomology of the resulting strong homotopy Lie algebra.