Cindy Aossey and Dee Crescitelli started the session with a notice and wonder about two graphs.
Our group’s noticings included:
- In the graceful numbering example, each red number is the difference between the circled numbers it connects on both graphs
- Each graph has the numbers 1-5 in black but not in the same places.
- The graphs do not lie on a coordinate plane
We also clarified the following terminology:
- Vertices (vertex) – the black circles
- Edges – connect two vertices
- Tree Graph – contains no cycles (loops)
After considering additional examples and non-examples of Graceful labeling, Cindy and Dee gave the following definition for gracefully labeling a tree graph:
- Vertices must be labeled distinctly from 1 through n (where n is the number of vertices).
- Edges must be labeled with the absolute value of the difference of the endpoint vertices.
- Edge labels must be distinct, or 1 through n-1.
Cindy and Dee shared the Ringel-Kotzig (Graceful Tree) Conjecture which states “All Trees are Graceful” (i.e. there is a way to gracefully label every tree). https://en.wikipedia.org/wiki/Graceful_labeling This is an open conjecture, though it has been solved for some classes of trees. The rest of the meeting was spent exploring some specific classes.
The group first considered star graphs. Participants looked for ways to gracefully label these examples, then generalize their method to any graph of this type.
Terminology was developed to discuss the graphs and two labeling strategies were discovered. Sophia, Rebecca and Marguerite labeled the center vertex with 1, then labeled all of the remaining vertices in order. Maggie pointed out that they don’t need to be labeled in order, but doing so makes it more clear that the graph has been successfully labeled.
Khom, Sarah and Vera started by giving the top vertex, which they called the origin, the largest label (or “n”) then labeling the remaining vertices from 1 to n-1.
The rest of the meeting was spent discussing this next class of graphs consisting of two connected stars.
Groups found many examples of graceful and non-graceful labels!
The following observation was made by at least two groups “If the three graph has n vertices, then the vertex labeled “1” and the vertex labeled “n” must be connected.” They used this observation to conclude that at least one of the top two vertices had to be labeled with 1 or n. At least one group looked for ways to label where the top two vertices were labeled 1 and n respectively. While not proven, this approach seems to work when the number of leaves branching off from each top nodes is even.
Examples of graceful labeling using 1 & n for the top two nodes with an even number of branches from each of these nodes:
Maya, Eric, Stephanie and Kevin found two general ways to gracefully label this class of graphs.
Following the yellow highlighted figure 8, number the vertices starting at 1, numbering in order to n. Alternatively, label in the same pattern starting at n. They shared that they actually focused on labeling the edges first, then determining what vertex labels would work. With that in mind, you can see that the edge labels start at 1 on the left and increase as you move left to right. They also knew that the largest edge label had endpoints of 1 and n. Eric had made a “baby conjecture” that top edge would be labeled with the middle edge value (e.g. if there are 7 edges, the top edge would be labeled 4.)
In the remaining few minutes, Dee & Cindy shared some general information about Graceful Labeling, all of which is available in the session slide deck here: https://docs.google.com/presentation/d/1VQ6dRptpOuFq-AAycX855LRq5LnUFR5PXVihDM535qk/edit?usp=sharing
