Self-avoiding walks of specified lengths on rectangular grid graphs

Abstract

<p>The investigation of self-avoiding walks on graphs has an extensive literature. We study the notion of wrong steps of self-avoiding walks on rectangular shape <span><em>n</em><span>×</span><em>m</em></span> grids of square cells (Manhattan graphs) and examine some general and special cases. We determine the number of self-avoiding walks with one and with two wrong steps in general. We also establish some properties, like unimodality and sum of the rows of the Pascal-like triangles corresponding to the walks. We also present particular recurrence relations on the number of self-avoiding walks on the <span><em>n</em><span>×</span><span>2</span></span> grids with any specified number of wrong steps. <br></p>