Create
Design Project Gallery
Counting Random Walk Labelings of Caterpillar Graphs
- Program: Applied Mathematics and Statistics
- Course: Other
- Year: 2025
Project Description:
We examine the total number of random walk labelings of various graphs, focusing specifically on caterpillar graphs. Random walk labelings are based on walks along graph edges where each previously unvisited vertex is labeled in increasing order. A caterpillar graph has a path of n vertices (the “backbone”), with additional vertices connected by edges (‘legs”) to the backbone. Each leg connects to only one backbone vertex, and leg vertices connected to different backbone vertices cannot be connected to each other; however, legs from the same backbone vertex may connect freely. We focus on symmetric caterpillars, where each backbone vertex has the same configuration of j legs. Configurations include standard caterpillars and those where legs induce a complete graph or path. We find a general formula for the number of labelings for any such symmetric configuration and derive a closed-form expression for the standard caterpillar of length n with j legs.
Project Photo:
As the name suggests, caterpillar graphs look a bit like caterpillars! On the bottom, we see a caterpillar graph (with a backbone of length four and two legs per backbone vertex) in a shape that parallels the caterpillar above, which similarly has two legs connected to each spiracle.