On general position sets in Cartesian grids
Sandi Klavžar, Gregor Rus, Ismael G. Yero · arXiv (Cornell University) · 2019
The general position number ${\rm gp}(G)$ of a connected graph $G$ is the cardinality of a largest set $S$ of vertices such that no three pairwise distinct vertices from $S$ lie on a common geodesic; such sets are refereed to as gp-sets of $G$. A formula for the number of gp-sets in $P_r \,\square\, P_s$, $r,s\ge 2$, is determined. The general position number of cylinders $P_r \,\square\, C_s$ is deduced, while ${\rm gp}(C_r \,\square\, C_s)$ is bounded from the below by $6$, whenever $r\ge s eq 4$ and $r\ge 6$. It is proved that ${\rm gp}(P_{\infty} \,\square\, P_{\infty} \,\square\, P_{\infty}) \ge 14$. A probabilistic lower bound on the general position number of Hamming graphs and of Cartesian graph powers is also achieved.