Regularity conjecture for graphs with lexicographically optimal Cartesian squares

Let $G$ be a graph, and consider the Cartesian square $G\times G$. An ordering of the vertices is optimal for the edge-isoperimetric problem (EIP) when it minimizes the number of boundary edges among vertex sets of each prescribed size. The lexicographic order on tuples is defined by declaring $(x_1,\dots,x_n)$ greater than $(y_1,\dots,y_n)$ if, for some $i$, one has $x_j=y_j$ for $1\leq j<i$ and $x_i>y_i$. Regularity conjecture. If the lexicographic order is optimal for $G\times G$, then $G$ is regular. The conjecture seeks to characterize graphs for which the lexicographic order is optimal on all Cartesian powers. The local-global principle shows that optimality for $G\times G$ implies optimality for $G^n$ for every $n\geq 3$, but no general method is known for establishing optimality on Cartesian squares of concrete graphs.