Create
Design Project Gallery
Counting Random Walk Labelings of Graphs
- Program: Applied Mathematics and Statistics
- Course: EN.553.500 Undergraduate Research
- Year: 2026
Project Description:
We examine the total number of random walk labelings of various graphs, with emphasis on
caterpillar graphs and modifications on caterpillar graphs. Our motivation is discovering new
integer sequences not in the OEIS, and establishing combinatorial identities for sequences
already existing in the OEIS. A random walk labeling of a graph is defined to be any labeling
obtainable by performing a random walk, wherein a walker walks randomly along the edges
of a graph. Each previously unvisited vertex is subsequently labeled in increasing order.
We derive closed form expressions for the total number of random walk labelings for the
standard caterpillar and its variants.
Project Photo:
Backbone graph and map to standard caterpillar
