On general position sets in Cartesian products

Sandi Klavžar; Balázs Patkós; Gregor Rus; Ismael G. Yero

paper

On general position sets in Cartesian products

arXiv:1907.04535

Abstract

The general position number $gp (G)$ of a connected graph $G$ is the cardinality of a largest set $S$ of vertices such that no three distinct vertices from $S$ lie on a common geodesic; such sets are refereed to as gp-sets of $G$ . The general position number of cylinders $P_{r} □ C_{s}$ is deduced. It is proved that $gp (C_{r} □ C_{s}) \in {6, 7}$ whenever $r \geq s \geq 3$ , $s \neq = 4$ , and $r \geq 6$ . A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in $P_{r} □ P_{s}$ , where $r, s \geq 2$ , is also determined.