Discrete Mathematics and Combinatorics Commons^™

Asymptotically Optimal Bounds For (𝑡,2) Broadcast Domination On Finite Grids, Timothy W. Randolph

Rose-Hulman Undergraduate Mathematics Journal

Let G = (V,E) be a graph and t,r be positive integers. The signal that a tower vertex T of signal strength t supplies to a vertex v is defined as sig(T, v) = max(t − dist(T,v),0), where dist(T,v) denotes the distance between the vertices v and T. In 2015 Blessing, Insko, Johnson, and Mauretour defined a (t, r) broadcast dominating set, or simply a (t, r) broadcast, on G as a set T ⊆ V such that the sum of all signal received at each vertex v ∈ V from the set of towers T …

A Generalized Newton-Girard Identity, Tanay Wakhare

Rose-Hulman Undergraduate Mathematics Journal

We present a generalization of the Newton-Girard identities, along with some applications. As an addendum, we collect many evaluations of symmetric polynomials to which these identities apply.

The Knill Graph Dimension From The Minimum Clique Cover, Kassahun Betre, Evatt Salinger

Faculty Publications

In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim(G1+G2)=1+dimG1+dimG2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order N will have dimension N−1. We finish by finding lower and upper bounds on the Knill dimension of a graph in terms of its clique number.

Two-Pebbling And Odd-Two-Pebbling Are Not Equivalent, Charles A. Cusack, Airat Bekmetjev, Mark Powers

Faculty Publications

Let G be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of G. A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. The pebbling number of G, denoted π(G), is the smallest integer such that any configuration of π(G) pebbles on G is solvable. A graph has the two-pebbling property if after placing more than 2π(G) -- q pebbles on G …

Singular Ramsey And Turán Numbers, Yair Caro, Zsolt Tuza

Theory & Applications of Graphs

We say that a subgraph F of a graph G is singular if the degrees d_G(v) are all equal or all distinct for the vertices v ∈ V (F). The singular Ramsey number Rs(F) is the smallest positive integer n such that, for every m at least n, in every edge 2-coloring of K_m, at least one of the color classes contains F as a singular subgraph. In a similar flavor, the singular Turán number Ts(n,F) is defined as the maximum number of edges in a graph of order n, …

Analysis Of Feast Spectral Approximations Using The Dpg Discretization, Jay Gopalakrishnan, Luka Grubišić, Jeffrey S. Ovall, Benjamin Quanah Parker

Mathematics and Statistics Faculty Publications and Presentations

A filtered subspace iteration for computing a cluster of eigenvalues and its accompanying eigenspace, known as “FEAST”, has gained considerable attention in recent years. This work studies issues that arise when FEAST is applied to compute part of the spectrum of an unbounded partial differential operator. Specifically, when the resolvent of the partial differential operator is approximated by the discontinuous Petrov Galerkin (DPG) method, it is shown that there is no spectral pollution. The theory also provides bounds on the discretization errors in the spectral approximations. Numerical experiments for simple operators illustrate the theory and also indicate the value of …

Computing Homology Of Hypergraphs, Jackson Earl

STAR Program Research Presentations

In the modern age of data science, the necessity for efficient and insightful analytical tools that enable us to interpret large data structures inherently presents itself. With the increasing utility of metrics offered by the mathematics of hypergraph theory and algebraic topology, we are able to explore multi-way relational datasets and actively develop such tools. Throughout this research endeavor, one of the primary goals has been to contribute to the development of computational algorithms pertaining to the homology of hypergraphs. More specifically, coding in python to compute the homology groups of a given hypergraph, as well as their Betti numbers …

Bounding The Number Of Compatible Simplices In Higher Dimensional Tournaments, Karthik Chandrasekhar

Theses and Dissertations--Mathematics

A tournament graph G is a vertex set V of size n, together with a directed edge set E ⊂ V × V such that (i, j) ∈ E if and only if (j, i) ∉ E for all distinct i, j ∈ V and (i, i) ∉ E for all i ∈ V. We explore the following generalization: For a fixed k we orient every k-subset of V by assigning it an orientation. That is, every facet of the (k − 1)-skeleton of the ( …

Squared Distance Matrix Of A Weighted Tree, Ravindra B. Bapat

Journal Articles

Let T be a tree with vertex set f1;: :: ; ng such that each edge is assigned a nonzero weight. The squared distance matrix of T; denoted by is the n n matrix with (i; j)-element d(i; j)2; where d(i; j) is the sum of the weights of the edges on the (ij)-path. We obtain a formula for the determinant of A formula for 1 is also obtained, under certain conditions. The results generalize known formulas for the unweighted case.

On Monochromatic Sets With Nondecreasing Diameter, Adam O’Neal

Theses, Dissertations and Capstones

Our problem comes from the field of combinatorics known as Ramsey theory. Ramsey theory, in a general sense, is about identifying the threshold for which a family of objects, associated with a particular parameter, goes from never or sometimes satisfying a certain property to always satisfying that property. Research in Ramsey theory has applications in design theory and coding theory. For integers m, r, and t, we say that a set of n integers colored with r colors is (m, r, t)-permissible if there exist t monochromatic subsets B₁, B₂, . . . , B_{t …}

On The Existence Of Partitioned Incomplete Latin Squares With Five Parts, Jaromy Kuhl, Donald Mcginn, Michael W. Schroeder

Mathematics Faculty Research

Let a, b, c, d, e be positive integers such that a ≤ b ≤ c ≤ d ≤ e. Heinrich showed the existence of a partitioned incomplete Latin square (PILS) of type (a, b, c) and (a, b, c, d) if and only if a = b = c and 2a ≥ d. For PILS of type (a,b,c,d,e), it is necessary that a + b + c ≥ e, but not sufficient, and no characterization is currently known. In this talk we provide an additional …

Modeling Stochastically Intransitive Relationships In Paired Comparison Data, Ryan Patrick Alexander Mcshane

Statistical Science Theses and Dissertations

If the Warriors beat the Rockets and the Rockets beat the Spurs, does that mean that the Warriors are better than the Spurs? Sophisticated fans would argue that the Warriors are better by the transitive property, but could Spurs fans make a legitimate argument that their team is better despite this chain of evidence?

We first explore the nature of intransitive (rock-scissors-paper) relationships with a graph theoretic approach to the method of paired comparisons framework popularized by Kendall and Smith (1940). Then, we focus on the setting where all pairs of items, teams, players, or objects have been compared to …

Lattice Simplices: Sufficiently Complicated, Brian Davis

Theses and Dissertations--Mathematics

Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields.

In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of …

Revisiting The Isoperimetric Graph Partitioning Problem, Sravan Danda, Aditya Challa, B. S. Daya Sagar, Laurent Najman

Journal Articles

Isoperimetric graph partitioning, which is also known as the Cheeger cut, is NP-hard in its original form. In the literature, multiple modifications to this problem have been proposed to obtain approximation algorithms for clustering applications. In the context of image segmentation, a heuristic continuous relaxation to this problem introduced by Leo Grady and Eric L. Schwartz has yielded good quality results. This algorithm is based on solving a linear system of equations involving the Laplacian of the image graph. Furthermore, the same algorithm applied to a maximum spanning tree (MST) of the image graph was shown to produce similar results …

Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich

Honors Theses

We find necessary and separate sufficient conditions for the difference between two labeled partially ordered set's (poset) partition generating functions to be positive in the fundamental basis. We define the notion of a jump sequence for a poset and show how different conditions on the jump sequences of two posets are necessary for those posets to have an order relation in the fundamental basis. Our sufficient conditions are of two types. First, we show how manipulating a poset's Hasse diagram produces a poset that is greater according to the fundamental basis. Secondly, we also provide tools to explain posets that …

Neutrosophic Triplet Structures - Vol. 1, Florentin Smarandache, Memet Sahin

Branch Mathematics and Statistics Faculty and Staff Publications

Neutrosophic set has been derived from a new branch of philosophy, namely Neutrosophy. Neutrosophic set is capable of dealing with uncertainty, indeterminacy and inconsistent information. Neutrosophic set approaches are suitable to modeling problems with uncertainty, indeterminacy and inconsistent information in which human knowledge is necessary, and human evaluation is needed. Neutrosophic set theory was firstly proposed in 1998 by Florentin Smarandache, who also developed the concept of single valued neutrosophic set, oriented towards real world scientific and engineering applications. Since then, the single valued neutrosophic set theory has been extensively studied in books and monographs, the properties of neutrosophic sets …

Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek

Graduate Theses, Dissertations, and Problem Reports (ETD)

In my dissertation, I present results on two types of edge coloring problems for graphs.

For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already …

Infinite Matroids And Transfinite Sequences, Martin Andrew Storm

Graduate Theses, Dissertations, and Problem Reports (ETD)

A matroid is a pair M = (E,I) where E is a set and I is a set of subsets of E that are called independent, echoing the notion of linear independence. One of the leading open problems in infinite matroid theory is the Matroid Intersection Conjecture by Nash-Williams which is a generalization of Hall’s Theorem. In [31] Jerzy Wojciechowski introduced µ- admissibility for pairs of matroids on the same ground set and showed that it is a necessary condition for the existence of a matching. A pair of matroids (M,W) with common ground set E is µ-admissible if a …

Gallai-Ramsey Number For Classes Of Brooms, Benjamin J. Hamlin

College of Graduate Studies: Theses & Dissertations

Given a graph $G$, we consider the problem of finding the minimum number $n$ such that any $k$ edge colored complete graph on $n$ vertices contains either a rainbow colored triangle or a monochromatic copy of the graph $G$, denoted $gr_k(K_{3}:G)$. More precisely we consider $G=B_{m,\ell}$ where $B_{m,\ell}$ is a broom graph with $m$ representing the number of vertices on the handle and $\ell$ representing the number of bristle vertices. We develop a technique to reduce the difficulty of finding $gr_{k}(K_{3}:B_{m,\ell})$, and use the technique to prove a few cases with a fixed handle length, but arbitrarily many bristles. Further, …

Inverse Problems Related To The Wiener And Steiner-Wiener Indices, Matthew Gentry

College of Graduate Studies: Theses & Dissertations

In a graph, the generalized distance between multiple vertices is the minimum number of edges in a connected subgraph that contains these vertices. When we consider such distances between all subsets of $k$ vertices and take the sum, it is called the Steiner $k$-Wiener index and has important applications in Chemical Graph Theory. In this thesis we consider the inverse problems related to the Steiner Wiener index, i.e. for what positive integers is there a graph with Steiner Wiener index of that value?

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

College of Graduate Studies: Theses & Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound …

Taking A Canon To The Adjunction Formula, Paul M. Harrelson

College of Graduate Studies: Theses & Dissertations

In this paper, we show how the canonical divisor of a graph is related to the canonical divisor of its subgraph. The use of chip firing and the adjunction formula for graphs ex- plains said relation and even completes it. We go on to show the difference between the formula for full subgraphs and that of non-full subgraphs. Examples are used to simplify these results and to see the adjunction formula in action. Finally, we show that though the adjunction formula seems simple at first glance, it is somewhat complex and rather useful.

Special Subset Vertex Multisubgraphs For Multi Networks, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilanthenral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors study special type of subset vertex multi subgraphs; these multi subgraphs can be directed or otherwise. Another special feature of these subset vertex multigraphs is that we are aware of the elements in each vertex set and how it affects the structure of both subset vertex multisubgraphs and edge multisubgraphs. It is pertinent to record at this juncture that certain ego centric directed multistar graphs become empty on the removal of one edge, there by theorising the importance, and giving certain postulates how to safely form ego centric multi networks. Given any subset vertex multigraph we …

Some Results On Partial Difference Sets And Partial Geometries, Eric J. Neubert Jr

Dissertations, Master's Theses and Master's Reports

This thesis shows results on 3 different problems involving partial difference sets (PDS) in abelian groups, and uses PDS to study partial geometries with an abelian Singer group. First, the last two undetermined cases of PDS on abelian groups with k ≤ 100, both of order 216, were shown not to exist. Second, new parameter bounds for k and ∆ were found for PDS on abelian groups of order p^n , p an odd prime, n odd. A parameter search on p^5 in particular was conducted, and only 5 possible such cases remain for p < 250. Lastly, the existence of rigid type partial geometries with an abelian Singer group are examined; existence is left undetermined for 11 cases with α ≤ 200. This final study led to the determination of nonexistence for an infinite class of cases which impose a negative Latin type PDS.

Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel

Theory & Applications of Graphs

For a simple connected graph G=(V,E) and a subset X of its vertices, let

d*(X) = max {dist}_G(x,y): x,y ∈ X}

and let h*(G) be the largest k such that there are disjoint vertex subsets A and B of G, each of size k such that d*(A) = d*(B). Let h*(n) = min {h*(G): |V(G)|=n}. We prove that h*(n) =⌊(n+1)/3 ⌋, for n ≥ 6. This solves the homometric set problem restricted to the largest distance exactly. In addition we compare h*(G) with a respective function h_diam(G), where …

Simplifying Coefficients In A Family Of Ordinary Differential Equations Related To The Generating Function Of The Laguerre Polynomials, Feng Qi

Applications and Applied Mathematics: An International Journal (AAM)

In the paper, by virtue of the Faà di Bruno formula, properties of the Bell polynomials of the second kind, and the Lah inversion formula, the author simplifies coefficients in a family of ordinary differential equations related to the generating function of the Laguerre polynomials.

Italian Domination On Ladders And Related Products, Bradley Gardner

Electronic Theses and Dissertations

An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination …

Finite Simple Graphs And Their Associated Graph Lattices, James B. Hart, Brian Frazier

Theory & Applications of Graphs

In his 2005 dissertation, Antoine Vella explored combinatorical aspects of finite graphs utilizing a topological space whose open sets are intimately tied to the structure of the graph. In this paper, we go a step further and examine some aspects of the open set lattices induced by these topological spaces. In particular, we will characterize all lattices that constitute the opens for finite simple graphs endowed with this topology, explore the structure of these lattices, and show that these lattices contain information necessary to reconstruct the graph and its complement in several ways.

A Proof Of The "Magicness" Of The Siam Construction Of A Magic Square, Joshua Arroyo

Rose-Hulman Undergraduate Mathematics Journal

A magic square is an n x n array filled with n² distinct positive integers 1, 2, ..., n² such that the sum of the n integers in each row, column, and each of the main diagonals are the same. A Latin square is an n x n array consisting of n distinct symbols such that each symbol appears exactly once in each row and column of the square. Many articles dealing with the construction of magic squares introduce the Siam method as a "simple'' construction for magic squares. Rarely, however, does the article actually prove that the …

On Orders Of Elliptic Curves Over Finite Fields, Yujin H. Kim, Jackson Bahr, Eric Neyman, Gregory Taylor

Rose-Hulman Undergraduate Mathematics Journal

In this work, we completely characterize by $j$-invariant the number of orders of elliptic curves over all finite fields $F_{p^r}$ using combinatorial arguments and elementary number theory. Whenever possible, we state and prove exactly which orders can be taken on.