Gracefully Labeling Spiders with all but at Most 2 Leg Lengths being at Most 2

Title

Gracefully Labeling Spiders with all but at Most 2 Leg Lengths being at Most 2

Files

Publication Date

4-2020

Document Type

Poster

Degree Type

Undergraduate

Department

Mathematics

Mentor

Songling Shan

Mentor Department

Mathematics

Abstract

Let G be a graph with m edges. A graceful labeling of G is a function f : V (G) → {0, 1, . . . , m} such that distinct vertices receive distinct numbers and {| f(u)−f(v) |: uv ∈ E(G)} = {1, 2, . . . , m}. We call G graceful if G has a graceful labeling. Rosa in 1966 firstly conjectured that every tree is graceful. This conjecture was only confirmed for certain classes of trees including caterpillar trees, lobster trees with a perfect matching. A spider is a tree with exactly one vertex of degree at least 3. Panpa and Poomsa-ard in 2016 proved that all spiders with all but at most four leg length being 1 are graceful. In this work, we show that every spider with all but at most two leg lengths being at most 2 is graceful. Our proof consists of finding a nice pattern in gracefully labeling two subgroups of spiders: every spider with all legs being length at most two, every spider with all but one leg being length at most two. In all these labelings, the value assigned to the center vertex is always zero. Finally, applying an approach introduced in [Gracefulness of families of spiders, P. Bahl, S. Lake, and A. Wertheim, G, Involve, 3 (2010) 241-247], we are able to find a graceful labeling for spiders with all but at most two leg lengths being at most 2.

Notes

This project has not received IRB approval.

Gracefully Labeling Spiders with all but at Most 2 Leg Lengths being at Most 2
COinS