Daniela Ferrero - Research Trends in Graph Theory and Applications

Focusing on the groundbreaking work of women in mathematics past, present, and future, Springer's Association for Women in Mathematics Series presents the latest research and proceedings of conferences worldwide organized by the Association for Women in Mathematics (AWM). All works are peer-reviewed to meet the highest standards of scientific literature, while presenting topics at the cutting edge of pure and applied mathematics, as well as in the areas of mathematical education and history. Since its inception in 1971, The Association for Women in Mathematics has been a non-profit organization designed to help encourage women and girls to study and pursue active careers in mathematics and the mathematical sciences and to promote equal opportunity and equal treatment of women and girls in the mathematical sciences. Currently, the organization represents more than 3000 members and 200 institutions constituting a broad spectrum of the mathematical community in the United States and around the world.

Titles from this series are indexed by Scopus.

More information about this series at http://www.springer.com/series/13764

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

This book contains a selection of research at the frontiers of current knowledge in a broad variety of different areas of graph theory and its applications. Research topics include edge-density conditions in multipartite graphs, graph searching, metric dimension, reconfiguration problems, creating chaos by breaking symmetries, and coding theory problems for the protection and accessibility of distributed data storage.

The research in this volume was performed by teams formed at the Workshop for Women in Graph Theory and Applications held at the Institute for Mathematics and its Applications (University of MinnesotaMinneapolis) on August 1923, 2019. During this workshop, 42 participants performed collaborative research in 6 teams, each focused on a different area of graph theory and its applications. Teams included experts in each area, who helped participants identify open problems to work on. After the workshop, all teams continued their collaborations remotely and solved some of the problems they started researching during the workshop. This book contains six chapters, and each of them is written by one of the research collaboration teams formed at the Workshop for Women in Graph Theory and Applications.

Chapter 1: Finding Long Cycles in Balanced Tripartite Graphs: A First Step

Gabriela Araujo-Pardo, Zhanar Berikkyzy, Jill Faudree, Kirsten Hogenson, Rachel Kirsch, Linda Lesniak, and Jessica McDonald

Intuitively, in a graph with no loops and no parallel edges, a high level of edge density implies the existence of long cycles. This observation leads to the problem of determining the minimum number of edges q such that an arbitrary graph with exactly p vertices and q edges necessarily has a cycle of length at least , a question especially interesting for large values of . In the case =p this question asks for the minimum number of edges such that every graph with order p has a cycle containing every single vertex exactly once, or a Hamiltonian cycle. The problem considered in this chapter is the existence of long cycles in balanced tripartite graphs. This chapter starts with a survey of the relevant literature, namely degree and edge conditions for the existence of long cycles in graphs, including the case of Hamiltonian cycles as well as improved conditions obtained in the case of bipartite and k-partite results where they exist. After this survey, the authors prove that if G is a balanced tripartite graph on 3n vertices, G must contain a cycle of length at least 3n1 provided that e(G)3n24n+5 and n14.

Chapter 2: Product Throttling

Sarah E. Anderson, Karen L. Collins, Daniela Ferrero, Leslie Hogben, Carolyn Mayer, Ann N. Trenk, and Shanise Walker

Propagation processes on graphs, such as zero forcing and power domination, and pursuit-evasion games, such as cops and robbers, involve an element of graph searching. Parameters indicating the amount of time that it takes to finish the process or search have been independently proposed in each case, and their study has produced interesting results. In this chapter the authors study the cost trade-off between time and resources when the process uses more than the minimum possible number of resources. Throttling addresses the question of minimizing the sum or the product of the resources used in a graph searching process and the time needed to complete the process. The study of throttling began with the study of sum throttling, and the forms of graph searching that have been studied include various types of zero forcing, power domination, and cops and robbers. Recently, two different definitions of product throttling have been introduced for cops and robbers and power domination. This chapter presents a summary of prior results for these two cases and introduces universal versions of the two definitions. Each of the definitions is then applied and studied for each of the following graph searching processes: standard zero forcing, positive semidefinite zero forcing, power domination, and cops and robbers.