On locally n \times n grid graphs

MaRDI QIDQ6315872zbMATH OpenFDO

Authors Carmen Amarra, Wei Jin, Cheryl E. Praeger

Publication date 19 March 2019

Abstract: We investigate locally $nimesn$ grid graphs, that is, graphs in which the neighbourhood of any vertex is the Cartesian product of two complete graphs on $n$ vertices. We consider the subclass of these graphs for which each pair of vertices at distance two is joined by sufficiently many paths of length $2$. The number of such paths is known to be at most $2n$ by previous work of Blokhuis and Brouwer. We show that if each distance two pair is joined by at least $n-1$ paths of length $2$ then the diameter is bounded by $O(log(n))$, while if each pair is joined by at least $2(n-1)$ such paths then the diameter is at most $3$ and we give a tight upper bound on the order of the graphs. We show that graphs meeting this upper bound are distance-regular antipodal covers of complete graphs. We exhibit an infinite family of such graphs which are locally $nimesn$ grid for odd prime powers $n$, and apply these results to locally $5imes5$ grid graphs to obtain a classification for the case where either all $mu$-graphs have order at least $8$ or all $mu$-graphs have order $c$ for some constant $c$.

This page was built for publication: On locally $n \times n$ grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315872)