Gracefulness of Spiders with Leg Length at Most Three with an Additional Leg of Arbitrary Length

Title

Gracefulness of Spiders with Leg Length at Most Three with an Additional Leg of Arbitrary Length

Files

Publication Date

4-2020

Document Type

Presentation

Presentation Type

Group

Degree Type

Undergraduate

Mentor

Songling Shan

Abstract

Let G be a graph with m edges. A graceful labeling of G injectively assigns integers from the set {0, 1, 2, . . . , m} to the vertices of G so that the absolute difference between each vertex includes every number in the set {1, 2, . . . , m}. We say that G is graceful if there exists a graceful labeling of G. Rosa in 1966 firstly proposed the following conjecture: every tree is graceful. This conjecture was only confirmed for certain classes of trees and still wide open. A spider is a tree that has exactly one vertex of degree at least three. Bahls, Lake, and Wertheim in 2010 proved that every spider with its leg length being in two consecutive values is graceful. In this work, we show that every spider with each leg length being at most 3 and one leg being an arbitrary length can be gracefully labeled.

Bahls, Lake, and Wertheim [Gracefulness of families of spiders, P. Bahl, S. Lake, and A. Wertheim, G, Involve, 3 (2010) 241-247] introduced a method of adding a leg of arbitrary length to a gracefully labeled spiders such that the central vertex is labeled by zero. The paper explains a method to gracefully label spiders with an odd number of legs and then uses the arbitrary leg method to add on another leg to gracefully label spiders with an even number of legs with consecutive leg lengths. The issue with the arbitrary leg method is that it requires that the central vertex to be previously labeled by zero, and the actual method will change the central vertex to go from 0 to 1 to 2 and onward. Therefore, you cannot use the arbitrary leg length method more than once. So in order to gracefully label spiders with an even amount of legs of length at most 3 with an additional leg of arbitrary length, we had to find a new approach. We solve this issue from two aspects. One strategy involves attempting to find a way to gracefully label spiders with an even number of legs of length at most 3 while keeping the central vertex labeled zero. This is being explored by the first author. The second strategy involves being able to add an arbitrary length leg while the central vertex is not 0. A method has been found and proven for this.

Notes

Authors: Anna Janaszak, Jacob Nottoli, Eva Yang

This project has not received IRB approval.

Gracefulness of Spiders with Leg Length at Most Three with an Additional Leg of Arbitrary Length
COinS