| Digital Archive


Search the Digital Archive

Permutations with Extremal Routings on Cycles

Show full item record

Author: Valentin, Luis Alejandro
Advisor: Yu, Gexin
Committee Members: Vinroot, C. Ryan; Torczon, Virginia
Issued Date: 2012
Subjects: Graph theory
Routing number
URI: http://hdl.handle.net/10288/16711
Description: 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.
Degree: Bachelors of Science in Mathematics

Files in this item

Files Size Format View Description
Valentin_thesis_complete.pdf 366.7Kb PDF View/Open Complete Thesis

This item appears in the following Collection(s)

Show full item record

Attribution-NonCommercial 3.0 United States Except where otherwise noted, this item's license is described as Attribution-NonCommercial 3.0 United States