International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 61, Pages 3291-3299

On the edge set of graphs of lattice paths

Steven Klee,1 Lara Pudwell,2 and Rick Gillman1

1Department of Mathematics and Computer Science, Valparaiso University, Valparaiso 46383, IN, USA
2Department of Mathematics, Rutgers University, Piscataway 08854, NJ, USA

Received 4 June 2003

Copyright © 2004 Steven Klee et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This note explores a new family of graphs defined on the set of paths of the m×n lattice. We let each of the paths of the lattice be represented by a vertex, and connect two vertices by an edge if the corresponding paths share more than k steps, where k is a fixed parameter 0=k=m+n. Each such graph is denoted by G(m,n,k). Two large complete subgraphs of G(m,n,k) are described for all values of m, n, and k. The size of the edge set is determined for n=2, and a complicated recursive formula is given for the size of the edge set when k=1.