2 problems

Let $P_n\square P_n$ be the Cartesian product of two paths on $n$ vertices, with vertices labelled so that $(0,0)$ is a corner. Let $\mathrm{sn}(G,(0,0))$ denote the maximum number…

Let $P_n$ be the path on $n$ vertices, and let $P_n\square P_n$ be the Cartesian product of two such paths. Write $\rho(G)$ for the expected percentage of vertices saved when a fir…