Thursday, August 25, 2011

Way to go Mrs. Stott

I mentioned in my presentation at ISAMA last June that the map operation snub, Sn(M), which is Mrs. Stott's expansion operation Ex(M) plus an added chiral edge, makes a diamond-pattern tensegrity from any base map. The bow, the kite frame (X-module tensegrity,) and the classic three-strut tensegrity are inventions that made their separate appearances in human history centuries apart. It is remarkable to see them all fall from Mrs. Stott's expansion operation when applied to the simplest maps.

It occurred to me last night (while relaxing at the Strathmore Ukelele Festival) that I had missed another remarkable property of this map operation: the resultant map is always hamiltonian. In particular, any spanning tree in the base map (it's guaranteed that there is at least one spanning tree in any connected map) specifies a hamiltonian circuit.

To see that this is true, consider a fanciful strategy of walking "around the outside" of a spanning tree of the map M in a counter-clockwise direction. This strategy lets us visit every vertex of the tree in a closed cycle, but at the cost of visiting every edge twice (seeing the edge as an isthmus, we will be traveling along it once on each shore and in opposite directions) and visiting each vertex a number of times equal to its valence in the tree. Mrs. Stott's expansion duplicates edges and vertices just enough (times-two for the edges; times-the-valence for the vertices) to eliminate these duplicated visits. That turns our fanciful trip around a spanning tree in the old map into a guaranteed hamiltonian circuit in the new map.

No comments: