PortalGraph Theory
Exploring Graph Theory.
This research project is in the mathematical area of graph theory, where a graph is a mathematical representation of relationships among entities. Formally, we describe it as a structure consisting of a collection of points, called vertices, and lines, called edges, joining pairs of points. In particular, we will focus on a type of graph labeling, called a graceful labeling, introduced by Alexander Rosa in 1967 and studied by hundreds of mathematicians since. [2] Although the formal definition may seem complicated, a graceful labeling of a graph with m edges is simply a labeling of the vertices that induces a labeling on the edges where we must satisfy a few conditions: (1) The labels on the vertices come from the set of integers between 0 and m. (2) The label of an edge is the positive difference of the labels of its incident vertices. (3) No two vertices have the same label. (4) No two edges have the same label.
The last two conditions require that a graceful labeling be vertex-distinguishing as well as edge-distinguishing. This leads to the many applications of graceful labelings to such things as radar detection, communication networks, ATM networks, and X-ray crystallography. [2], [4] However, it has been proven by Graham and Sloane that almost all graphs are not graceful. [3] If we are looking at an especially large and/or real-life network, we may not have the luxury of being able to assign it a graceful labeling. This motivates us to investigate ways of distinguishing vertices and edges from each other, even when the graph we have is not graceful.
Although this project is motivated by applications, its execution will be rooted in pure mathematics. We will be using logical reasoning, experimentation, and fundamental proof techniques to explore (and hopefully determine) a method of distinguishing vertices and/or edges in a variety of complicated graph structures. We will focus as much on the research process as the results; together, we will develop questions to ask and investigate, work on examples to further understanding, extrapolate to make conjectures based on our findings, then formally prove our claims.
Prerequisites: Students must have strong logical reasoning skills and a desire to learn fundamental proof techniques. Prior exposure to basic proof techniques, perhaps in a Discrete Mathematics or Intro Proofs course, is preferred but not necessary. Prior knowledge of Graph Theory is not necessary.
References
[1] U. Deshmukh, Applications of Graceful Graphs. International Journal of Engineering Sciences & Research Technology. (2015) pp. 129-131.
[2] R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs. SIAM J. Alg. Disc. Math. 1 (1980) pp. 382-404.
[3] A. Rosa, On certain valuations of the vertices of a graph. Theory of Graphs. (International Symposium, Rome, July 1966), (1967) pp. 349-355.
[4] R. Sivaraman. Graceful Graphs and Its Applications. International Journal of Current Research. (2016) Vol. 8, Issue, 11, pp. 41062-41067.
Short Bio
Dr. Alexis Byers (she/her/hers) is an Assistant Professor at Youngstown State University. Her love for pure mathematics, and graph theory in particular, began during her undergraduate education at Wittenberg University, where she eventually earned her B.S. in Mathematics. Dr. Byers had her first taste of research in an REU at Miami University, and thus she began her path toward graduate school and eventually a career in academia. Dr. Byers earned her PhD in Mathematics from Western Michigan University in 2018, and she joined the faculty at Youngstown State University the following fall. At YSU, Dr. Byers works on research in graph theory in such topics as Ramsey theory, graph labelings, and graph colorings. Moreover, Dr. Byers has advised numerous research projects in graph theory and combinatorics with a variety of students, ranging from those in high school to those in graduate programs. Her goal for all her research students is to challenge their perception of mathematics and to show them that they can contribute to the field in a meaningful way.
