[+] Team 1: Edge conditions in k-partite graphs
- Mentor Jill Faudree, University of Alaska
- Mentor Linda Lesniak, Western Michigan University
If a graph has “a lot” of edges, then it is more likely to have properties like being hamiltonian, containing a given subgraph, etc. For many of these properties there are sufficient degree conditions and also conditions based on the number of edges.
Our team will concentrate on edge conditions for various graph properties and how these conditions may be improved by restricting our graphs to be k-partite. A graph G is k-partite if the vertex set can be partitioned into k sets so that every edge joins vertices in different sets. In the 1960’s Moon and and Moser studied hamiltonicity in balanced bipartite graphs, that is, k-partite for k = 2, This was extended to an edge condition for hamiltonicity in balanced 3-partite graphs by Adamus in 2009. Finally, an edge condition for hamiltonicity in all k-partite graphs was very recently obtained by Ferrero and Lesniak. These edge conditions improved those for general graphs. Our team will investigate sufficient edge conditions for other graph properties when the graphs under consideration are k-partite. How many edges in a k-partite graph G with n vertices guarantees a perfect matching in G? A copy of a given graph in G? That G is hamiltonian connected? In each case the goal is to improve the result for general graphs.
[+] Team 2: Graph searching
- Mentor Daniela Ferrero, Texas State University-San Marcos
- Mentor Leslie Hogben, Iowa State University
Research will comprise various forms of graph searching, including zero forcing, power domination, and Cops & Robbers. The graph processes of power domination and zero forcing are involved in the analysis of electrical network monitoring and other applications, and pursuit-evasion games such as Cops & Robbers can be used to analyze intrusion detection; all contain an element of graph searching. For each of these parameters, the amount of time that it takes to finish the process (time cost) is also studied. The cost trade-off between time and resources when the process uses more than the minimum possible number of resources is called throttling and is another active area of research.
[+] Team 3: Data storage, protection and accessibility
- Mentor Christine Kelley, University of Nebraska
- Mentor Gretchen Matthews, Virginia Polytechnic Institute and State University
The massive amount of data generated in today’s society leads to challenges in data storage, protection, and accessibility. Graphs show up in all of these settings. For example, distributed storage systems can be built from path decompositions of regular graphs. The goal is quick recovery of a disk with the minimum amount of communication on the graph. This prompts the consideration of cage graphs which may be used to maximize the number of disk erasures recoverable relative to the total number of disks in the system. Another topic is the use of graph based decoders to obtain low complexity decoding for codes, such as low-density parity-check codes. While such decoders offer phenomenal performance most of the time, careful analysis using techniques from combinatorial optimization demonstrates how and when failure occurs. Graphs may also be employed to yield codes which are locally decodable, locally correctable, or locally recoverable. This is important in applications where it is necessary to determine messages or code word symbol(s) with only random access to the received word, in contrast to the traditional setting where a decoder takes as input a received word w and uses all coordinates of w to produce an estimate of the code word originally sent.
[+] Team 4: The metric dimension of a graph
- Mentor Linda Eroh, University of Wisconsin at Oshkosh
- Mentor Ortud Oellermann, University of Winnipeg
Research will focus on the metric dimension and its variants, including the strong dimension, the partition dimension and metric location domination numbers. The metric dimension has arisen in numerous applications as for example, in network security, the navigation of robots in a graph space, coin weighing problems and strategies for the master mind game. Computing these parameters is in general hard. We propose to study how these invariants behave within families of well-structured graphs. We will also study heuristics that allow us to give good bounds for these invariants.
[+] Team 5: Creating chaos by breaking graph symmetries
- Mentor Debra Boutin, Hamilton College
- Mentor Sally Cockburn, Hamilton College
Graph distinguishing involves coloring the vertices to “destroy” all symmetry. That is, vertices are colored so that no non-trivial symmetry will also preserve vertex colors. The smallest number of colors required to do this is called the distinguishing number. If only two colors are needed the graph is 2- distinguishable. In this case, one can ask what is the least number of times a second color is actually needed. This is the cost of 2-distinguishing. A set of vertices that uniquely identifies the symmetries in the graph is called a determining set and the size of the smallest such set is called the determining number. The determining set helps in understanding the rigidity of the graph. Though first defined and studied separately, it turns out that a smallest color class in a 2-distinguishing coloring is a determining set, but not necessarily of smallest size. This means the determining number is a lower bound on the cost of 2- distinguishing.
[+] Team 6: Reconfiguration problems
- Mentor Ruth Haas, University of Hawaii at Manoa
- Mentor Karen Seyffarth, University of Calgary
Reconfiguration is a very active area of research in combinatorics. Broadly speaking, given a problem with multiple solutions, reconfiguration studies whether it is possible to move from one solution to another following a given set of rules. For example, let G be a graph, and r > x(G) a number of colors, is it possible to get from one proper r coloring of G to another by a sequence of vertex changes so that each step along the way is a proper coloring? Questions in reconfiguration include: is it possible to move from one solution to another? What is the complexity of determining if it is possible? How many steps does it take to reconfigure? The reconfiguration graph is a graph whose vertices are all feasible solutions to the problem, with an edge between them if one can be obtained from another by one application of the reconfiguration rule. What are the properties of the reconfiguration graph for a given or general reconfiguration problem? Eg., number of connected components, diameter? This project will concern reconfiguration of a graph theory problem such as coloring or domination.