On the edge set of graphs of lattice paths (Q1777851)

Let \(m,n, k\) be positive integers. The authors investigate the structure of families of graphs defined in the following way: the vertices of a graph \(G(m,n,k)\) correspond to the distinct paths in an \(m\times n\) rectangular lattice and two vertices are connected by an edge whenever the corresponding paths share more than \(k\) steps. A characterisation of two large complete subgraphs of \(G(m,n,k)\) and some results for the number of edges of \(G(m,n,k)\) are provided.