2019 Projects
19.02 - Sum Index Graphs
Participants: Kedar Karhadkar, Eugene Henninger-Voss, Emily Robinson
Mentors: Tony Wong, Josh Harrington
Summary of project:
Definition 0.1. Let G be a simple graph with vertex set V and edge set E. Let f : V → Z be an injective vertex labeling of G, and let f+ : E → Z be an induced edge labeling defined by f+(uv) = f(u) +f(v) for any edge uv in E. The sum index of G is the minimum positive integer k such that there exists an injective vertex labeling f of G with the cardinality of the range of f+ being k.
Some results that we currently have include:
• the sum index of a complete graph Kn is 2n − 3 for all positive integers n ≥ 2;
• the sum index of a complete bipartite graph Kn,m is n + m − 1 for all positive integers n and m;
• the sum index of a caterpillar graph G is ∆, where ∆ is the maximum degree of G;
• the sum index of a tree G with diameter at most 5 is ∆, where ∆ is the maximum degree of G;
• there exists a tree with diameter 6 such that the sum index of G is greater than ∆, where ∆ is the maximum degree of G;
• the sum index of a tree G with diameter D is at most [D/2]∆, where ∆ is the maximum degree of G.
Results:
Let G be a nonempty simple graph with a vertex set V and an edge set E. For every injective vertex labeling, f, from V to the integers, there are two induced edge labelings, namely, f+, from E to the integers, defined by the sum of f for the endpoints of an edge and f- to be the absolute value of the difference in f evaluated at the endpoint. The sum index and the difference index are the minimum cardinalities of the ranges of f+ and f-, respectively. We give the upper and lower bounds on the sum index and difference index, and determine the sum index and difference index of various families of graphs.
19.04 - Random Race
Participants: Kedar Karhadkar, Tessa Stevens, Madeline Kohutka, Sabrina Traver
Mentors: Tony Wong, Josh Harrington
Summary of project:
Alice and Bob play the following game: they take turns to collect 1 or 2 chips randomly and independently with equal probability, with Alice going first. The first person who collects at least n chips is the winner. We have determined that the winning probability of Bob is...
Results:
Alice and Bob take turns to collect chips in the following manner. In each turn, Alice tosses a fair coin, which decides whether she collects a or b chips, where a and b are positive integers. If Alice collects a chips, then Bob collects b chips, and vice versa. We consider two variants of game play that have different rules in determining the winner. Namely, the winner of Game 1 is the first player to collect at least n chips, while the winner of Game 2 is the first player to collect a positive number of chips congruent to 0 modulo n. We fully determine the formula for the winning probabilities of each player in Game 1, and determine the best and worst case scenarios in terms of winning probabilities in Game 2.
Paper submitted for random race, titled "Two dependent probabilistic chip-collecting games."
19.05 - Networks
Participants: Bryan Walker, Elise Anderson, Cristian Hernandez, Rey Anaya, Alvaro Belmonte, Peterson Lenard
Mentors: Nate Shank
Summary of project:
Assume a network can be represented by a graph G with vertex set V and edge set E. The network is operational as long as the graph maintains some property P. The network reliability measures how quickly a network loses property P. Often vertices fail, or edges fail, or both. Often we use this information backwards; meaning we want to construct a network with maximum reliability relative to property P, however we are restricted by the number of vertices and edges in the graph. Given n vertices, m edges, and property P, what graphs will produce the most (and least) reliable networks? The aid of computers allows us to experiment with small values of n and m in order to make conjectures.
Results:
The team developed a new network reliability measure related to dominating number. For any positive integer, k, The k-super bondage number of a graph G is the minimum number of edges that must be removed so that the dominating number increases by k. When k=1, this is the bondage number which has been discussed in previous literature. The group found graphs where successive bondage moves is not as effective as doing the 2-super bondage. This means that sometimes it is better to be inefficient to increase the dominating number by one so that you can more easily increase the dominating number by 2. We concluded by trying to find the most and least reliable graphs for graphs of a fixed size and order.
19.07 - G-Designs
Participants: Eugene Henninger-Voss, Froylan Maldonado, Alvaro Belmonte
Mentors: James Hammer
Summary of project:
A G-design of order n is a decomposition of the complete graph on n vertices into edge-disjoint subgraphs isomorphic to G. The spectrum for decomposing the complete graph into trees with up to 8 edges has been studied and the spectrum problem for cycles has been completely solved. A Halin Graph is defined by a tree whose leaves have been joined into a cycle. In this project, we will investigate the feasibility of determining necessary and sufficient conditions for the existence of a Halin-design for trees with fewer than eight edges
Results:
Where we started off is certainly not where we ended up, but that is okay. That’s how research goes sometimes. The students really took the reins on this and made it their own. We began the REU by trying to decompose the complete graph into edge disjoint 3-regular Halin Graphs. That is to say, we were trying to find a 3-regular Halin graph inside of the complete graph, pluck it out, and then repeat this process until there were no longer any edges left. We had some preliminary results on this front; however, discovered that most of these cases were covered in previous literature under the guise of graph labeling. Once we discovered this, we attempted larger 3-regular Halin Graphs, but this quickly became cumbersome; so we switched gears a bit. For the second half of the REU, this group examined triangle decompositions of Kneser graphs. That is to say that instead of decomposing the complete graph, we were trying to decompose a slightly sparser graph into edge disjoint triangles. Some of the low hanging fruit has been done by Braxton Carrigan, Aaron Clark, and James Hammer; however, their proposed construction is something that some of these authors plan on perusing in the future. There is one piece of their construction that has yet to be shown can be decomposed, but if the authors can show it, it will certainly be worthy of a publication.
19.08 - Perm Graphs
Participants: Robert Argus, Tessa Stevens, Elise Anderson
Mentors: Caitlin Owens
Summary of project:
The Hamiltonian path problem is a well-known NP-complete graph theory problem which is to determine whether or not it is possible to find a path through all the vertices of a graph, visiting each vertex exactly once. A variation on this problem is the 1HP problem which is to determine, given a graph and a vertex in the graph, whether or not it is possible to find a Hamiltonian path in the graph which has the specified vertex as an end of the path. The problem is also NP-complete for graphs in general, though like the Hamiltonian path problem, 1HP can be polynomially solvable on certain types of graphs. Bipartite permutation graphs is a class of graphs for which the problem is known to be polynomially solvable. In this project, we will investigate whether there are structural properties of bipartite permutation graphs which can determine whether or not there is a Hamiltonian path which has an end at a given vertex.
Results:
This project developed into a new one as the REU progressed. In our efforts to determine structural properties in a bipartite permutation graph with a specified vertex to have a Hamiltonian path with that vertex as a path endpoint, our group created programs to produce bipartite permutation graphs. Using this program, we were able to count the permutations which produced graphs with certain Hamiltonian-related properties, and by the end of the REU we discovered many interesting sequences from them.
19.09 - Colored Paths
Participants: Emily Robinson, Rey Anaya, Madeline Kohutka, Chen Sun
Mentors: Caitlin Owens, James Hammer
Summary of project:
An edge coloring of a graph is a proper edge coloring if incident edges are colored with distinct colors. A properly colored path in a graph is a path such that the edges of the path are properly edge colored. A graph, with an edge coloring, is said to be properly connected if there is a properly colored path between every pair of vertices. In this project, we will investigate the minimum number of colors required to color the edges such that every shortest path between a pair of vertices is properly colored
Results:
To be consistent with the literature, we defined the very strong proper connection number of a graph to be the minimum number of colors required to edge color the graph so that every shortest path between any pair of vertices is properly colored. We began the REU by determining the very strong proper connection number for basic graphs, like cycle graphs, complete graphs, wheel graphs, and trees.
From there, we were able to determine the very strong proper connection number for triangle-free graphs (which include cycles and trees). We ended the REU with determining the very strong proper connection number for block graphs. The proof of this last class led us to a conjecture for the very strong proper connection number for graphs in general. We are still in the process of trying to prove this conjecture.
19.10 - Plates and Olives
Participants: Robert Argus, Bryan Walker, Cristian Hernandez, Benjamin Nagle
Mentors: Gene Fiorini
Summary of project:
The game of plates and olives begins with an empty plate. At each step either an empty plate is put down, an olive is put down on a plate, an olive is removed, an empty plate is removed, or the olives of two plates are combined on one plate with the other plate being removed. A game of plates and olives can be represented by ordered trees with with n vertices of degree 3 and n + 2 vertices of degree one. The game derives from the consideration of Morse functions on the 2-sphere. An excellent Morse function on the 2-sphere is defined as a function in which all the critical points are non-degenerate. The number of topological equivalence classes of excellent Morse functions on the 2-sphere that have order n (that is, they have 2n +2 critical points) is the same as the number of ways of returning to an empty table for the first time after exactly 2n + 2 steps. We call this number M(n). Upper and lower bounds are known for M(n), but exact values are known only for n <15. This project will examine M(n) by studying families of ordered trees with n vertices of degree 3 and n + 2 vertices of degree 1.
Results:
19.11 - Latin Squares
Participants: Sabrina Traver, Froylan Maldonado, Peterson Lenard
Mentors: Gene Fiorini, Tony Wong
Summary of project:
Considering a randomly generated collection of samples allows an unbiased investigation of collections that are too extensive to be investigated exhaustively. For example, for each positive integer n, let Dn denote the set of integers consisting of every number that is the determinant of an n by n Latin square. There are many questions concerning the elements of Dn. For instance: For which odd n is 0 in Dn? For which n is n(1 + 2 + ... + n) in Dn?
Results:
19.12 - Pebbling
Participants: Benjamin Nagle, Chen Sun, Shihao Feng, Auroni Hashim
Mentors: Gene Fiorini
Summary of project:
A good edge-labeling of a graph is a labeling of its edges such that for any ordered pair of vertices u and v, there is at most one non-decreasing path from u to v. A graph is good if it admits a good edge-labeling. This project will examine if graphs of large girth admit a good edge-labeling.
Results: