Files
Download Poster (165 KB)
Publication Date
4-2020
Document Type
Poster
Presentation Type
Individual
Degree Type
Undergraduate
Department
Mathematics
Mentor
Songling Shan
Mentor Department
Mathematics
Abstract
Given a graph G with m edges, we can describe this graph as graceful or not. A graph that is graceful has a function f : V (G) → {0, 1, 2, ...m} so that distinct vertices receive distinct numbers and the set defined by {|f(u)−f(v)| : uv ∈ V (G)} is equivalent to the set {1, 2, 3, ...m}. Put simply, we want to be able to label the vertices of the graph in such a way where the absolute difference between the end vertices of an edge is unique. If there is a way to label the graph following these stipulations then we say that the graph is graceful, and if there is no such way that graph is not graceful. In this project we look at all order six graphs and categorize them as graceful or not. Using a compiled list of order six graphs, we are able to take all non-isomorphic graphs with their respective adjacency matrices and find if they are graceful or not. To do this we created a program in Java which takes the adjacency matrix as an input, and outputs all ways to gracefully label the graph if any. The program uses several steps to try and minimize the total number of cases we need to check, and does so in a few different ways. In order for a graph with n vertices to be graceful, it must have at least n−1 edges, else there would not be enough elements in the set {0, 1, 2...m} to distinctly label the vertices. So we check this first, then move on to the sets of possible numbers themselves, as not every set of numbers has all possible differences we need. The program works with all graphs no matter the order, however for larger graphs the program may take some time to execute, as the time function is one that grows exponentially with the order of the graph. Below are two examples of order six graphs. The larger numbers are the vertex labels, and the smaller ones are the edge labels. To the left is a labeling of the Complete Graph that is not graeful. As you can see there are repeated edge numbers, so this labeling is not graceful. In fact, there are no ways to gracefully label the complete graph using numbers from the set {0, 1, 2, ...15}, so we say that the graph itself is not graceful. On the right is a graceful graph, with one way to label it gracefully. On the left is the complete graph on six vertices, which is not graceful. On the right is an order six graph that was found to be graceful.
Recommended Citation
Kirk, Samuel, "Graceful Labelings of Order Six Graphs" (2020). Mathematics. 6.
https://ir.library.illinoisstate.edu/ursmat/6
Notes
This project has not received IRB approval.