| Digital Archive


Search the Digital Archive

Factoring Banded Permutations and Bounds on the Density of Vertex Identifying Codes on the Infinite Snub Hexagonal Grid

Show full item record

Author: Albert, Chase A.
Advisor: Yu, Gexin
Committee Members: Vinroot, C. Ryan; Torczon, Virginia
Issued Date: 2011
URI: http://hdl.handle.net/10288/17073
Description: A permutation may be characterized as b-banded when it moves no element more than b places. Every permutation may be factored into 1-banded permutations. We prove that an upper bound on the number of tridiagonal factors necessary is 2b-1, verifying a conjecture of Gilbert Strang. A vertex identifying code of a graph is a subset D of the graph's vertices with the property that for every pair of vertices v1 and v2, N[v1]∩D and N[v2]∩D are distinct and nonempty, where N[v] is the set of all vertices adjacent to v, including v. We compute an upper bound of 1/3 and a strict lower bound of 3/10 for the minimum density of a vertex identifying code on the infinite snub hexagonal grid.
Degree: Bachelors of Science in Mathematics

Files in this item

Files Size Format View
Chase_Albert_thesis.pdf 606.5Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record