2
$\begingroup$

There are many (planar) lattices: standard square grid lattice, hexagonal lattice, triangular lattice, Lieb lattice, Kagome lattice, dice lattice...

Consider the standard square lattice on $\mathbb Z^2$ (each vertex has valency four) and add `non-crossing' diagonals to each face of this graph (we do not add any new vertices). Now each vertex has valency eight.

(An equivalent way to define this graph is to say that each point of $\mathbb Z^2$ is connected with the 8 nearest neighbors.)

Is there a name for such a graph? I have seem something like `a strong product of two infinite paths', but I cannot make any sense of it.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ I have seen it called the “infinite king grid” or “king’s lattice,” after the king piece in chess; see en.wikipedia.org/wiki/King%27s_graph $\endgroup$
    – ho boon suan
    Commented Jun 21, 2023 at 17:02
  • 3
    $\begingroup$ I would call it the $\ell_\infty$ grid, since we're joining lattice points at $||\cdot||_\infty$ distance one. $\endgroup$
    – Joshua Erde
    Commented Jun 21, 2023 at 20:11
  • $\begingroup$ Why do you say "non-crossing diagonals": the diagonals you add do cross one another, no? $\endgroup$
    – Sam Hopkins
    Commented Jun 21, 2023 at 22:09
  • $\begingroup$ @SamHopkins yes, they do cross... What I mean is that that these diagonals are edges of a graph. An equivalent way to define this graph is to say that each vertex is connected to the 8 nearest neighbors. $\endgroup$
    – Nikita Kalinin
    Commented Jun 22, 2023 at 6:13

1 Answer 1

Reset to default
4
$\begingroup$

Indeed, as ho boon suan mentioned, this graph is called King's graph.

And indeed it is a strong product of two infinite paths.

A strong product of two graphs $(V,E),(V',E')$ has $V\times V'$ as the vertex set, and the edge set is the set of $((v_1,v_1'),(v_2,v_2')$ if

  1. $v_1=v_2, (v_1',v_2')\in E'$ or
  2. $v_1'=v_2', (v_1,v_2)\in E$ or
  3. $(v_1,v_2)\in E, (v_1',v_2')\in E'$.

also sometimes it is called an EHM lattice (see here)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Apparently EHM stands for "extended Harper model". $\endgroup$
    – Zach Teitler
    Commented Jun 22, 2023 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .