Date Thesis Awarded
Bachelors of Science (BS)
C. Ryan Vinroot
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.
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. Paper 557.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.