#### Date Thesis Awarded

2012

#### Document Type

Honors Thesis

#### Degree Name

Bachelors of Science (BS)

#### Department

Mathematics

#### Advisor

Gexin Yu

#### Committee Member

C. Ryan Vinroot

#### Committee Member

Virginia Torczon

#### Abstract

Let G be a graph on n vertices labeled v_1,...,v_n. Suppose that on each vertex there is a pebble, p_j, which has a destination of v_j. During each step, a disjoint set of edges is selected and the pebbles on an edge are swapped. The routing problem asks what the minimum number of steps necessary for any permutation of the pebbles to be routed so that for each pebble, p_i is on v_i. Li, Lu, and Yang prove that the routing number of a cycle of n vertices is equal to n-1. They conjecture that for n >= 5, if the routing number of a permutation on a cycle is n-1, then the permutation is (123...n) or its inverse. We prove that the conjecture holds for all even n.

#### Recommended Citation

Valentin, Luis Alejandro, "Permutations with Extremal Routings on Cycles" (2012). *Undergraduate Honors Theses.* Paper 500.

http://publish.wm.edu/honorstheses/500

#### Creative Commons License

This work is licensed under a Creative Commons Attribution-Noncommercial 3.0 License

## Comments

Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.