Date Thesis Awarded
2011
Access Type
Honors Thesis -- Access Restricted On-Campus Only
Degree Name
Bachelors of Science (BS)
Department
Mathematics
Advisor
Gexin Yu
Committee Members
C. Ryan Vinroot
Virginia Torczon
Abstract
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.
Recommended Citation
Albert, Chase A., "Factoring Banded Permutations and Bounds on the Density of Vertex Identifying Codes on the Infinite Snub Hexagonal Grid" (2011). Undergraduate Honors Theses. William & Mary. Paper 557.
https://scholarworks.wm.edu/honorstheses/557
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Comments
Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.