Removing the minimum number of vertices or points from a square lattice such that no square path exists is known as the square path problem. Finding this number as the size of the lattice increases is not so trivial. Results provided by Erdos-Posa and Bienstock-Dean provides an upper bound for eliminating all cycles from a planar graph but sheds little light on the case of the square lattice. This paper provides several values for the minimum number of vertices needed to be removed such that no square path exists.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/17386 |
| Date | January 2000 |
| Creators | Williams, Nikki LaTrina |
| Contributors | Dean, Nathaniel |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | Thesis, Text |
| Format | 41 p., application/pdf |
Page generated in 0.0883 seconds