# Truncated codes and ternary cube compounds

###### Abstract

Perfect codes in the $n$-dimensional grid $\Lambda_{n}$ of $\mathbb{Z}^{n}$
($0<n\in\mathbb{Z}$) and its quotient toroidal grids were obtained via the
truncated distance $\rho(u,v)$ in $\mathbb{Z}^{n}$ given between
$u=(u_{1},\cdots,u_{n})$ and $v=(v_{1},\ldots,v_{n})$ in $\mathbb{Z}^{n}$ as
the graph distance $h(u,v)$ in $\Lambda_{n}$ if $|u_{i}-v_{i}|\leq 1$, for all
$i\in\\{1,\ldots,n\\}$, and as $n+1$, otherwise. Such perfect codes are
extended to non-lattice superlattice graphs $\Gamma_{n}$ obtained by glueing
ternary $n$-cubes along each of their codimension 1 ternary subcubes. We
ascertain the existence of an infinite number of isolated perfect truncated-
metric codes of radius 2 in $\Gamma_{n}$ for $n=2$ and conjecture such
existence for $n>2$ with radius $n$. We ask whether there are suitable notions
replacing quotient toroidal grids of $\Lambda_{n}$ for the case of
$\Gamma_{n}$.

###### keywords:

Truncated metric, perfect code, square lattice, ternary cube

Italo DejterI. DejterUniversity of Puerto Rico
Rio Piedras, PR<EMAIL_ADDRESS>Luis FuentesL.
FuentesUniversidad Nacional Abierta y a Distancia
Cartagena<EMAIL_ADDRESS>Carlos AraujoC.
AraujoUniversidad del Atlantico
Barranquilla<EMAIL_ADDRESS>94B25; 52C22;
11H31; 05C69

##  1 Perfect truncated-metric codes

We are motivated by computer architecture problems (cf [1]) associated to
signal transmission in a finite field (cf. [10, 11, 14]) including algorithm-
flowchart modeling with applications in alternate reality games. Related
topics of coding theory and lattice domination are based on the Lee metric
arising from the Minkowsky $\ell_{p}$ norm [4] with $p=1$. These themes,
related to the still unsolved Golomb-Welch Conjecture [13, 15, 16], were
investigated via perfect Lee codes [10], diameter perfect Lee codes [14],
tilings with generalized Lee spheres [2, 11], perfect dominating sets (PDS’s)
[20], perfect-distance dominating sets (PDDS’s) [1] and efficient dominating
sets [8].

Let $0<n\in\mathbb{Z}$. The aforementioned codes or dominating sets are
realized in the lattice tiling of $\mathbb{Z}^{n}$, whose tiles are translates
of a common generalized Lee sphere. This lattice tiling happens in the
$n$-dimensional grid $\Lambda_{n}$, namely the lattice graph whose vertex set
is $\mathbb{Z}^{n}$ with exactly one edge between each two vertices at
euclidean distance 1. A natural follow-up here was to consider lattice tilings
of $\mathbb{Z}^{n}$ with two different generalized Lee spheres. Focus on such
follow-up for $n>3$ was only possible by modifying the notion of Lee distance
$d$ to that of a truncated distance $\rho$, defined below (not a standard
distance, but see Remark 5), having perfect code applications as in Subsection
1.3 that restates rainbow-coloring results of [12]. Furthermore, ternary non-
lattice superlattice graphs $\Gamma_{n}$, built as compounds of ternary
$n$-cubes glued along codimension 1 ternary subcubes, presented below in
Remark 1 and Section 2 that generalize the corresponding lattice graphs
$\Lambda_{n}$ (even though those are not lattice graphs themselves), extend
the mentioned perfect code applications in Section 3.

Recall that the Hamming distance $h(u,v)$ between vectors
$u=(u_{1},\cdots,u_{n})$ and $v=(v_{1},\ldots,v_{n})$ in
$\mathbb{Z}^{n}\subset\mathbb{R}^{n}$ is the number of positions
$i\in[n]=\\{1,\ldots,n\\}$ for which $u_{i}\neq v_{i}$. Now, let
$\rho:\mathbb{Z}^{n}\times\mathbb{Z}^{n}\rightarrow\mathbb{Z}$ be given by:

$\rho(u,v)=\cases{h}(u,v),\mbox{ if }|u_{i}-v_{i}|\leq 1\mbox{ for all
}i\in[n];\\\ n+1,\mbox{ otherwise}\\}.$

Given $S\subseteq\mathbb{Z}^{n}$, we denote by $[S]$ the induced subgraph of
$S$ in $\Lambda_{n}$. In the above definition of $\rho$, the Hamming distance
$h$ may be replaced alternatively by the graph distance in $\Lambda_{n}$ and
is also our choice definition to be used on the graphs $\Gamma_{n}$ of
Sections 2-3. Such graphs may be taken as alternate reality graphs, since they
offer from each vertex of a ternary $n$-cube glued in the compound
$\Gamma_{n}$ two ternary options as arrows for each coordinate direction. We
start by developing $\Gamma_{2}$ in Section 2. From each vertex of
$\Gamma_{n}$ algorithm flowcharts can be adapted following ternary directions
in participating ternary $n$-cubes, with vertices representing decision
conditional diamonds that lead to “Yes” or “True” and “No” or “False” arrows,
i.e. oriented edges representing two sides of a participating triangle in a
ternary $(n-1)$-cube, each such arrow representing one or more process
rectangles. An elementary example of this is given in Section 4.

To each component $H$ of $[S]$, we assign an integer $t_{H}>0$ to be
understood in the context below as the radius of a truncated sphere with
center $H$. For every component $H^{\prime}$ of $[S]$ in the translation class
$\langle H\rangle$ of $H$ in $\mathbb{Z}^{n}$, we assume
$t_{H^{\prime}}=t_{H}$. This yields a correspondence $\kappa$ from the set of
translation classes $\langle H\rangle$ of components $H$ of $[S]$ into
$\mathbb{Z}$ such that $\kappa(\langle H\rangle)=t_{H}$, for every
$H\in\langle H\rangle$.

Let $\rho(u,S)=\min\\{\rho(u,s)|s\in S\\}$. Let $(H)^{\kappa(\langle
H\rangle)}=\\{u\in\mathbb{Z}^{n}|\rho(u,H)\leq\kappa(\langle H\rangle)\\}$. A
$\kappa$-perfect truncated-metric code, or $\kappa$-PTMC, is a set
$S\subseteq\mathbb{Z}^{n}$ such that $\forall u\in\mathbb{Z}^{n}$ there exists
a unique $s\in S$ with $\rho(u,s)=\rho(u,S)$ and such that the collection

$\\{(H)^{\kappa(\langle H\rangle)}|H\mbox{ is a connected component of }S\\}$

forms a partition of $\mathbb{Z}^{n}$. For each component $H$ of $S$,
$(H)^{\kappa(\langle H\rangle)}$ is referred to as the truncated sphere
centered at $H$ (or around $H$) with radius $\kappa(\langle H\rangle)$. Here,
$H$ is said to be the truncated center of $(H)^{\kappa(\langle H\rangle)}$ and
its vertices are said to be its central vertices. Given $0<t\in\mathbb{Z}$, a
$\kappa$-PTMC is said to be a $t$-PTMC if all $\kappa(\langle H\rangle)$’s are
equal to $t$. If $|H|=1$, then $|(H)^{t}|=\sum_{i=0}^{t}2^{i}{n\choose i}$,
for $0\leq t\leq n$, (which is less than the cardinal of the corresponding
$\ell_{1}$ sphere of radius $t$, if $t>1$ [4]). We note that 1-PTMC’s coincide
with PDS’s [20].

######  Remark 1.

A binary (resp. ternary) $n$-cube graph $Q_{n}^{i}$, succinctly called
$n$-cube (resp. $n$-tercube), is a cartesian product
$K_{i}\square\cdots\square K_{i}$ of $n$ complete graphs $K_{i}$ with
$V(K_{i})=\\{0,\ldots,i-1\\}=F_{i}$, the field of order $i=2$ (resp. $3$). In
Sections 2\- 3, we extend the study of PTMC’s to edge-disjoint unions
$\Gamma_{n}\supset\Lambda_{n}$ of triangles; these are connected unions of
ternary $n$-cubes to be called ternary $n$-cube compounds, (denomination that
make us think of $\Lambda_{n}$ as binary $n$-cube compounds) and that cannot
have non-isolated PDS’s or non-isolated 1-PTMC’s. (However, the ternary
perfect single-error-correcting codes of length $\frac{3^{t}-1}{2}$ [18, 2]
are isolated PDS’s, or efficient dominating sets [8] in the ternary
$\frac{3^{t}-1}{2}$-cubes; these also are edge-disjoint unions of triangles,
for $t>0$). We will say for $G=\Gamma_{n}$ in Sections 2-3 that: an edge-
disjoint union $G$ of triangles has a non-isolated PDS $S$ if every vertex of
$G$ not in $S$ is adjacent to just either one vertex of $G$ (as in PDS’s) or
the two end-vertices of an edge of $S$. Therefore, a non-isolated PDS is not
necessarily a PDS. Section 3 shows that $\Gamma_{2}$ has an infinite number of
isolated 2-PTMC and conjectures that $\Gamma_{n}$ has isolated $n$-PTMC’s,
$\forall n>2$.

Figure 1: Example accompanying Remark 2

######  Remark 2.

We will restate some results of [12] in Theorem 1.2, (resp. Theorems 1.3-1.4)
below, in terms of PTMC’s: these results, given from a coloring-graph
viewpoint in [12], say that PTMC’s in $\Lambda_{n}$ that are lattice as in
[14], or lattice-like as in [1], exist having every induced component $H$ with
vertex set (a) whose convex hull is an $n$-parallelotope (resp. either a
0-cube or an $(n-1)$-cube) and (b) contained in and dominating a truncated
sphere centered at $H$ with radius $n$ (resp. radius either $n-2$ or 1) that
is a tile of the associated lattice tiling of $\mathbb{Z}^{n}$. In the center-
left of Figure 1, such 0-cubes and $(n-1)$-cubes are suggested in black and
dark-gray colors for $n=3$ (Theorem 1.3), representing $\mathbb{Z}^{n}$ with
dark-gray thin-edges and vertices, but dominating edges in thick black trace
and other edges of a specific tile in thick dark-gray trace. This is
schematized on the upper-right of the figure that represents the assignment of
the last coordinate value mod 3 on the projection of this PTMC onto
$\mathbb{Z}^{n-1}$. The case $n=4$ of Theorem 1.4 (the first PTMC which is
neither PDS nor PDDS), can be visualized similarly. For example, the
dominating edges, red colored in the copy of $Q^{2}_{4}\subset\mathbb{Z}^{4}$
in the lower-right of Figure 1 indicate a truncated sphere of radius 2 (resp.
1) at $(0,0,0,0)$ (resp. $(1,1,1,1)$). Also in the center-left of Figure 1,
light-gray 3-parallelotopes represent convex hull parts of truncated 3-spheres
whose central vertices form a lattice PTMC, the simplest case of Theorem 1.2.

######  Remark 3.

(I) A $t$-PTMC (resp. a truncated $t$-sphere) of $\Lambda_{n}$ is defined like
a PDDS [1] (resp. generalized Lee sphere [11]) with $\rho$ instead of the Lee
distance $d$. (II) 1-PTMC’s of $\Lambda_{n}$ (resp. truncated 1-spheres)
coincide with PDS’s [20] (resp. generalized Lee 1-spheres). (III) An example
[1] cited in Remark 7, below, justifies that our definition of PTMC above
employs translation classes instead of isomorphism classes, for in it the
truncated spheres have common radius (namely 1) for both translation classes,
but that does not exclude the eventuality of an example with differing radii.

######  Remark 4.

Motivation for Theorems 1.3-1.4 on building “lattice” $\kappa$-PTMC’s whose
induced components are $r$-cubes ($0\leq r\leq n$) of different dimensions $r$
comes from: (A) the perfect covering codes with spheres of two different radii
in Chapter 19 [5] and (B) a negative answer [19] to a conjecture [20] claiming
that the induced components of every 1-PTMC $S$ in an $n$-cube $Q^{2}_{n}$ are
all $r$-cubes $Q^{2}_{r}$ (not necessarily in the same translation class [9]),
where $r$ is fixed. In fact, it was found in [19] that a 1-PTMC in
$Q^{2}_{13}$ whose induced components are $r$-cubes $Q^{2}_{r}$ of two
different values $r=r_{1}$ and $r=r_{2}$ exists, specifically for $r_{1}=4$
and $r_{2}=0$. This seems to be the only known counterexample to the cited
conjecture.

###  1.1 Notation, $\ell_{p}$ metrics and periodicity

If no confusion arises, every $(a_{1},\ldots,a_{n})\in\mathbb{Z}^{n}$ is
expressed as $a_{1}\cdots a_{n}$. Let $O=00\cdots 0$, $e_{1}=10\cdots 0$,
$e_{2}=010\cdots 0$, $\ldots$, $e_{n-1}=0\cdots 010$ and $e_{n}=00\cdots 01$.

Let $z\in\mathbb{Z}^{n}$, let $H=(V,E)$ be a subgraph of $\Lambda_{n}$ and let
$H+z$ be the subgraph $H^{\prime}=(V^{\prime},E^{\prime})$ whose vertex set is
$V^{\prime}=V+z=\\{w\in\mathbb{Z}^{n};\exists\;v\in V$ such that $w=v+z\\}$ so
that $uv\in E$ $\Leftrightarrow$ $(u+z)(v+z)\in E^{\prime}$. For example, let
$H$ be induced in $\Lambda_{n}$ by the vertices with entries in $\\{0,1\\}$.
Then, every translation $H+z$ of $H$ in $\Lambda_{n}$ (in particular $H$
itself) is isomorphic to $Q^{2}_{n}$.

Let $i\in[n]$. Each edge (resp. segment) $uv$ of $\Lambda_{n}$ (resp.
$\mathbb{R}^{n}\supset\mathbb{Z}^{n}$) with $u\neq v$ is parallel to
$Oe_{i}\in E(\Lambda_{n})\Leftrightarrow u-v\in\\{\pm e_{i}\\}$ (resp.
$\Leftrightarrow\exists a\in\mathbb{R}\setminus\\{0\\}$ with $u-v=ae_{i}$). A
parallelotope $\mathcal{P}$ in $\mathbb{R}^{n}$ is a cartesian product of
segments parallel to some of the $Oe_{i}$’s ($i\in[n]$). We restrict to
$\mathcal{P}$’s having their vertices in $\mathbb{Z}^{n}$. An edge of
$\mathcal{P}$ is a segment of unit length parallel to some $Oe_{i}$
($i\in[n]$) separating a pair of vertices of $\Lambda_{n}$ in $\mathcal{P}$.
Recall that a trivial subgraph of $\Lambda_{n}$ is composed by just one
vertex. The proof of the following is similar to that of Theorem 1 [1].

######  Theorem 1.1.

Let $0<t\in\mathbb{Z}$. If $S$ is a $t$-PTMC in $\Lambda_{n}$, then the convex
hull in $\mathbb{R}^{n}$ of the vertex set $V(H)$ of each nontrivial component
$H$ of $[S]$ is a parallelotope in $\mathbb{R}^{n}$ whose edges are parallel
to some or all of the segments $Oe_{i}$ in $E(\Lambda_{n})$, where $i\in[n]$.

Let $H$ be a nontrivial induced subgraph of $\Lambda_{n}$ with the convex hull
of $V(H)$ in $\mathbb{R}^{n}$ as a parallelotope whose edges are parallel to
some or all of the segments $Oe_{i}$ in $E(\Lambda_{n})$, ($i\in[n]$). If
exactly $r$ elements of $[n]$ are such values of $i$, then we say that $H$ is
an $r$-box. Note that $H$ is a cartesian product $\Pi_{i=1}^{n}P^{i}$, where
$P^{i}$ is a finite path, $\forall i\in[n]$, with exactly $r$ paths $P^{i}$
having positive length.

Let $W_{n,H,t}$ be the truncated sphere of radius $t$ around an $H$ as above,
where $0\leq t\in\mathbb{Z}$. Then, $H$ is the truncated center of
$W_{n,H,t}$. A $t$-PTMC $S$ of $\Lambda_{n}$ determines a partition of
$\mathbb{Z}^{n}$ into spheres $W_{n,H,t}$ with $H$ running over the components
of $[S]$. Such an $S$ with the components of $[S]$ obtained by translations
from a fixed finite graph $H$ is said to be a $t$-PTMC$[H]$. (This imitates
the definition of a $t$-PDDS$[H]$ in [1], mentioned in Remark 3(I) above). Let
$S$ be a $t$-PTMC$[H]$ and let $H^{\prime}$ be a component of $[S]$ obtained
from $H$ by means of a translation. Then $S$ is said to be a lattice
$t$-PTMC$[H]$ if and only if there is a lattice $L\subseteq\mathbb{Z}^{n}$
such that: $H^{\prime\prime}$ is a component of $[S]$ $\Leftrightarrow$
$H^{\prime\prime}=H^{\prime}+z$, for some $z\in L$.

######  Remark 5.

It is relevant to note the connections of $\rho$ and the $\ell_{p}$ metrics
[4]: A truncated sphere of truncated radius 1 centered at some vertex $v$ is a
Lee ($p=1$) sphere of radius 1, whereas a truncated sphere of truncated radius
$n$ centered at $v$ is a sphere of radius 1 in the maximum ($p=\infty$)
distance, namely $W_{n,\\{v\\},1}$ (which has an $n$-dimensional cube for
convex hull). Thus, all truncated spheres in this work are spheres in some
$\ell_{p}$ metric, and the truncated metrics are a convenient way to consider
different $\ell_{p}$ metrics for the graph components. This observation allows
connections with other previous works such as (for just one $t$) perfect codes
in the maximum metric and in the $\ell_{p}$ metrics [4].

######  Remark 6.

We start to rephrase the graph-coloring facts of [12], to be completed in
Subsection 1.3. Announced as Theorem 1.2 below, there is a construction of
lattice $n$-PTMC’s $S$ whose induced subgraphs $[S]$ in $\Lambda_{n}$ have
their components $H$ with:

  1. (i)

vertex sets $V(H)$ whose convex hulls are $n$-boxes in $\mathbb{R}^{n}$ with
distance 3 to $[S]\setminus H$, and representatives (one per component $H$)
forming a lattice with generators along the coordinate directions;

  2. (ii)

each $V(H)$ contained in a truncated sphere $(H)^{\kappa(\langle H\rangle)}$
whose radius is $n$.

(We do not know whether similar lattice $t$-PTMC’s $S$ exist with $[S]$ having
$r$-parallelotopes as their components, for $r$ fixed such that $0<r<n$.)

Extending the meaning of the adjective lattice in Subsection 1.2 below, as in
[12] we have in Theorems 1.3-1.4 that a lattice $\kappa$-PTMC $S$ exists in
$\Lambda_{n}$ whose induced subgraph $[S]$ has its components $H$ with vertex
sets $V(H)$:

  1. (i′)

having both $(n-1)$-cubes and $0$-cubes as their convex hulls in
$\mathbb{R}^{n}$;

  2. (ii′)

contained in truncated spheres $(H)^{\kappa(\langle H\rangle)}$ whose radii,
namely 1 and $(n-2)$, correspond respectively to the $(n-1)$-cubes and 0-cubes
in item (i′).

A set $S\subset\mathbb{Z}^{n}=E(\Lambda_{n})$ is periodic if and only if there
exist $p_{1},\ldots,p_{n}$ in $\mathbb{Z}$ such that $v\in S$ implies $v\pm
p_{i}e_{i}\in S,\forall i\in[n]$. Since each lattice $t$-PTMC$[H]$ $S$ is
periodic [1], then every canonical projection from $\Lambda_{n}$ onto a
toroidal grid $\mathcal{T}$, i.e. a cartesian product
${\mathcal{T}}=C_{k_{1}p_{1}}\square C_{k_{2}p_{2}}\square\cdots\square
C_{k_{n}p_{n}}$ of $n$ cycles $C_{k_{i}p_{i}}$ ($0<k_{i}\in\mathbb{Z},\forall
i\in[n]$), takes $S$ onto a $t$-PTMC$[H]$ in $\mathcal{T}$. This observation
adapts to respective situations that complement the statements of Theorems
1.2-1.4 via canonical projections from $\mathbb{Z}^{n}$ onto adequate toroidal
grids $\mathcal{T}$.

Phys. Rev. B Do lattice $t$-PTMC’s $S$ exist with $[S]$ having
$r$-parallelotopes as their components, for $r$ fixed such that $0<r<n$?

###  1.2 Further specifications

Given a lattice $L$ in $\mathbb{Z}^{n}$, a subset $T\subseteq\mathbb{Z}^{n}$
that contains exactly one vertex in each class mod $L$ (so that $T$ is a
complete system of coset representatives of $L$ in $\Lambda_{n}$) is said to
be an FR (acronym suggesting “fundamental region”) of $L$. A partition of
$\mathbb{Z}^{n}$ into FR’s of $L$ is said to be a tiling of $\mathbb{Z}^{n}$.
Those FR’s are said to be its tiles.

We extend the notion of lattice $\kappa$-PTMC so that the associated
fundamental region (see [3], pg 26), or FR (see above) of every new lattice
contains a finite number of (in our applications, just two) members $H$ of
each $\langle H\rangle$.

In the literature, existing constructions of lattice $t$-PTMC’s in
$\Lambda_{n}$ ($t<n$) concern just $t=1$ (see [1, 2, 11, 14]) but there are
not many known lattice $1$-PTMC’s. For example, [7] shows that there is only
one lattice $1$-PTMC$[Q^{2}_{2}]$ and no non-lattice $1$-PTMC$[Q^{2}_{2}]$. In
addition, there is a lattice 2-PDDS$[Q^{2}_{1}]$ in $\Lambda_{3}$ arising from
a tiling of Minkowsky cited in [1].

There is no $t$-PTMC lattice in $\Lambda_{n}$, for $1<t<n$.

This conjecture has an analogous form for perfect codes in the $\ell_{p}$
metrics in [4], and together with the conjecture mentioned in Remark 4(B),
produces a contrast with the constructions in Theorems 1.3-1.4, below.

If $S$ is a periodic non-lattice $t$-PTMC$[H]$ in $\Lambda_{n}$, then there
exists $0<m\in\mathbb{Z}$ and a tiling of $\Lambda_{n}$ with tiles that are
disjoint copies of the vertex set $V(H^{*})$ of a connected subgraph $H^{*}$
induced in $\Lambda_{n}$ by the union of:

  1. (a)

the vertex sets of $m$ disjoint copies $H^{1},\ldots,H^{m}$ of $H$ (components
of $[S]$);

  2. (b)

the sets $(H^{j})^{\kappa(\langle H\rangle)}$ of vertices $v\in\mathbb{Z}^{n}$
with $\rho(v,H^{j})\leq t$, for $j\in[m]$, where

$(H^{1})^{\kappa(\langle H\rangle)},\ldots,(H^{m})^{\kappa(\langle H\rangle)}$
are pairwise disjoint copies of $(H)^{\kappa(\langle H\rangle)}$ in
$\mathbb{Z}^{n}$.

By taking such an $m$ as small as possible, we say that $S$ is a
$t$-PTMC$[H;m]$.

######  Remark 7.

In Section 5 [1], a non-lattice $1$-PTMC$[Q^{2}_{1};4]$ $S$ is shown to exist
with a lattice $L_{S}$ based on it, each of the FR’s of $L_{S}$ containing two
copies of $Q^{2}_{2}$ parallel to $Oe_{1}$ and two more copies of $Q^{2}_{2}$
parallel to $Oe_{2}$, these four copies being components of $[S]$.

Thus, even for a non-lattice $t$-PTMC $S$ in a $\Lambda_{n}$, a lattice can be
recovered and formed by selected vertices $v_{T}$ in the corresponding tiles
$T$ associated with $S$. We say that such set $S$ is a lattice
$t$-PTMC$[H;m]$, indicating the number $m$ of isomorphic components of $[S]$
in a typical tile $T$ in which to fix a distinguished vertex $v_{T}$.

We further specify the developments above as follows. A $t$-PTMC $S$ in
$\Lambda_{n}$ with the components of $[S]$ obtained by translations from two
non-parallel subgraphs $H_{0},H_{1}$ of $\Lambda_{n}$ is said to be a
$t$-PTMC$[H_{0},H_{1}]$. The case of this in Remark 7 is a $\kappa$-PTMC, with
two translation classes of components of $[S]$ formed by the copies of
$Q^{2}_{2}$ parallel to each of the directions coordinates. Here, $\kappa$
sends those copies onto $t=1$. Each tile of this $\kappa$-PTMC contains two
copies of $Q^{2}_{2}$ parallel to $Oe_{1}$ and two copies of $Q^{2}_{2}$
parallel to $Oe_{2}$, accounting for $m=4$.

More generally, let $t_{i}\in[n]$, for $i=0,1$. We say that a set $S\subset V$
is a $(t_{0},t_{1})$-PTMC$[H_{0},H_{1}]$ in $\Lambda_{n}$ if for each $v\in V$
there is:

  1. (i′′)

a unique index $i\in\\{0,1\\}$ and a unique component $H_{v}^{i}$ of $[S]$
obtained by means of a translation from $H_{i}$ such that the truncated
distance $\rho(v,H_{v}^{i})$ from $v$ to $H_{v}^{i}$ satisfies
$\rho(v,H_{v}^{i})\leq t_{i}$ and

  2. (ii′′)

a unique vertex $w$ in $H_{v}^{i}$ such that $\rho(v,w)=\rho(v,H_{v}^{i})$.

Even though such a set $S$ is not lattice as in [14] (or lattice-like [1]), it
may happen that there exists a lattice $L_{S}\subset\mathbb{Z}^{n}$ such that
for $0<m_{0},m_{1}\in\mathbb{Z}$ there exists an FR of $L_{S}$ in
$\Lambda_{n}$ given by the union of two disjoint subgraphs
$H^{*}_{0},H^{*}_{1}$, where $H^{*}_{i}$ ($i=0,1$) is induced in $\Lambda_{n}$
by the disjoint union of:

  1. (a′)

the vertex sets of $m_{i}$ disjoint copies $H_{i}^{1},\ldots,H_{i}^{m_{i}}$ of
$H_{i}$, (components of $[S]$);

  2. (b′)

the sets $(H_{i}^{j})^{\kappa(\langle H\rangle)}$ of vertices
$v\in\mathbb{Z}^{n}$ for which $0<\rho(v,H_{i}^{j})\leq t_{i}$ , for
$j\in[m_{i}]$, where $(H_{i}^{1})^{\kappa(\langle
H\rangle)},\ldots,(H_{i}^{m_{i}})^{\kappa(\langle H\rangle)}$ are pairwise
disjoint copies of $H^{\kappa}(\langle H\rangle))$ in $\mathbb{Z}^{n}$.

Subsection 1.3 contains a restatement of results of [12], translating its
graph-coloring context into our present one. In fact, in Theorem 1.3 below, a
lattice $1$-PTMC$[H_{0},H_{1};m_{0},m_{1}]$ is obtained; in addition, a family
of lattice $(t_{0},t_{1})$-PTMC$[H_{0},H_{1};m_{0},m_{1}]$’s in the graphs
$\Lambda_{n}$ that extend the lattice $1$-PTMC of Theorem 1.3 is obtained in
Theorem 1.4.

###  1.3 Restatement of graph-coloring results

A particular case of lattice $t$-PTMC$[H]$ is that in which $H$ is an $n$-box
of $\Lambda_{n}$. For each such $H$, Theorem 1.2 below says that there is a
lattice $n$-PTMC$[H]$ in $\Lambda_{n}$. (In [2], $n$-boxes of unit volume in
$\Lambda_{n}$ are shown to determine $1$-PDDS$[H]$’s if and only if either
$n=2^{r}-1$ or $n=3^{r}-1$).

How to construct a lattice $n$-PTMC$[H]$ $S$ in $\Lambda_{n}$? From Subsection
1.1 we know that $S$ determines a partition of $\mathbb{Z}^{n}$ into spheres
$W_{n,H^{\prime},n}$, where $H^{\prime}$ runs over the components of $[S[$.
These spheres must conform a tiling associated to a lattice
$L_{S}\subset\mathbb{Z}^{n}$ as follows: In each $W_{n,H^{\prime},n}$, let
$b_{1}b_{2}\cdots b_{n}$ be the vertex $a_{1}a_{2}\cdots a_{n}$ for which
$a_{1}+a_{2}+\cdots+a_{n}$ is minimal. We say that this $b_{1}b_{2}\cdots
b_{n}$ is the anchor of $W_{n,H^{\prime},n}$. The anchors of the spheres
$W_{n,H^{\prime},n}$ form the lattice $L=L_{S}$. Without loss of generality we
can assume that $O$ is the anchor of a $W_{n,H_{0},n}$ whose truncated center
$H_{0}$ is a component of $[S]$. Let $c_{1}c_{2}\cdots c_{n}$ be the vertex
$a_{1}a_{2}\cdots a_{n}$ in $W_{n,H_{0},n}$ for which
$a_{1}+a_{2}+\cdots+a_{n}$ is maximal. Then $L_{S}$ has generating set
$\\{(1+c_{1})e_{1},(1+c_{2})e_{2},\ldots,(1+c_{n})e_{n}\\}$ and is formed by
all linear combinations of those $(1+c_{i})e_{i}$, ($i\in[n]$). This insures
that $S$ exists and is lattice [14] (or lattice-like [1]) via $L_{S}$.

######  Theorem 1.2.

[12] For each $i\in[n]$, let $P_{i}$ be a path of length $c_{i}-2$, parallel
to $Oe_{i}$, and let $H=\Pi_{i=1}^{n}P_{i}$ be an $n$-box in $\Lambda_{n}$.
Then, there is a lattice $n$-PTMC$[H]$ $S$ of $\Lambda_{n}$ with minimum
$\ell_{1}$-distance 3 between the components of $[S]$.

As in Theorem 1.2 and commented in Remark 2, Figure 1 displays a
representation of the convex hulls of two induced components, in light-gray
color, of a lattice $t$-PTMC$[H]$ in $\Lambda_{n}$, where $t=n=3$ and
$H=Q^{2}_{0}$. The components of this PTMC are just 0-cubes, the simplest case
of Theorem 1.2 whose proof, discussed below, is contained in [12] from a
graph-coloring perspective.

######  Theorem 1.3.

[12] There exists a lattice $1$-PTMC$[Q^{2}_{2},Q^{2}_{0};2,2]$ (in particular
a PDS) $S$ in $\Lambda_{3}$ with minimum $\ell_{1}$-distance 3 between the
components of $[S]$.

As also commented in Remark 2, Theorem 1.3 is illustrated in Figure 1, showing
in black color the components of $[S]$ in a typical FR of $L_{S}$, namely: two
copies of $Q^{2}_{2}$ and two copies of $Q^{2}_{0}$, with the edges in the
corresponding truncated 1-spheres shown in thick black trace; the other edges
induced in the union of these 4 components are shown in thick dark-gray trace.
As also commented in Remark 2, truncated 3-spheres of the 3-PTMC$[Q^{2}_{0}]$
resulting from Theorem 1.2 are shaded in light-gray color. Also, dark-gray
color was used to indicate two other copies of $Q^{2}_{2}$ appearing in the
figure that are components of $[S]$. Notice that the vertices
$O,e_{1},e_{2},e_{3}$ are indicated in the figure.

To state Theorem 1.4, let $H_{0}=Q^{2}_{n-1}$, $H_{1}=Q^{2}_{0}$,
$m_{0}=m_{1}=2$, $t_{0}=1$, $t_{1}=n-2$.

######  Theorem 1.4.

There exists a lattice $(1,n-2)$-PTMC$[Q^{2}_{n-1},Q^{2}_{0};2,2]$ $S$ in
$\Lambda_{n}$.

######  Remark 8.

From the last observation in Remark 6, it can be deduced that the respective
PTMC $S$ covers (via canonical projections) in Theorems 1.2, 1.3 and 1.4,
respectively:

  1. $\bullet$

an $n$-PTMC$[H]$ in ${\mathcal{T}}=$ $C_{c_{1}k_{1}}\square
C_{c_{2}k_{2}}\square\cdots\square
C_{c_{n}k_{n}},(1<k_{i}\in\mathbb{Z},\forall i\in[n]);$

  2. $\bullet$

a $1$-PTMC$[Q^{2}_{2},Q^{2}_{0};2,2]$ in ${\mathcal{T}}=$ $C_{6k_{1}}\square
C_{6k_{2}}\square C_{3k_{3}},(0<k_{i},\forall i\in[3]);$

  3. $\bullet$

a $(1,n-2)$-PTMC$[Q^{2}_{n-1},Q^{2}_{0};2,2]$ in ${\mathcal{T}}=$
$C_{6k_{1}}\square\dots\square C_{6k_{n-1}}\square C_{3k_{n}},(0<k_{i},\forall
i\in[n]).$

##  2 Ternary superlattice graphs

Let the 2-tercube, or tersquare, $Q_{2}^{3}$ be denoted $[\emptyset]$, with
vertices given by the 2-tuples $xy$, ($x,y\in F_{3}=\\{0,1,2\\}$). As a graph,
$[\emptyset]=(0,1,2)\square(0,1,2),$ namely the cartesian product of two
triangles whose vertex sets are both $F_{3}$, is represented at the center of
Figure 2 sharing a triangle with each one of 15 tersquares, to be specified
below, in respective partially viewable colored backgrounds. The 1-sub-
tercubes or triangles $Q_{1}^{3}$ of the 2-tercube $[\emptyset]$ have vertex
sets $\\{0y\\}_{y\in F_{3}}$, $\\{1y\\}_{y\in F_{3}}$, $\\{2y\\}_{y\in
F_{3}}$, $\\{x0\\}_{x\in F_{3}}$, $\\{x1\\}_{x\in F_{3}}$, $\\{x2\\}_{x\in
F_{3}}$. They will be indicated $x^{0}$, $x^{1}$, $x^{2}$, $y^{0}$, $y^{1}$,
$y^{2}$, respectively. To each of these triangles $t^{s}$ ($t\in\\{x,y\\};s\in
F_{3}$) of $[\emptyset]$ we glue a corresponding tersquare $[^{t}_{s}]$
intersecting $[\emptyset]$ exactly in $t^{s}$.

TABLE I

$\begin{array}[]{||ccccccccccc||ccccccccccc||}\hline\cr\hline\cr
01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11&02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\\
|\\!\\!\\!&\\!\\!\\![^{xxyy}_{0110}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{010}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{yy}_{10}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{110}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{1010}]\\!\\!\\!&\\!\\!\\!|&|\\!\\!\\!&\\!\\!\\![^{xxyy}_{0220}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{020}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{yy}_{20}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{220}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{2020}]\\!\\!\\!&\\!\\!\\!|\\\
00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10&00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\\
|\\!\\!\\!&\\!\\!\\![^{xxy}_{011}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{01}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{1}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{11}]\\!\\!\\!&\\!\\!\\!|&[^{xxy}_{101}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{022}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{02}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{2}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{22}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{202}]\\!\\!\\!&\\!\\!\\!|\\\
01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11&02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\\
|\\!\\!\\!&\\!\\!\\![^{xx}_{01}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{0}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![\emptyset]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{1}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xx}_{10}]\\!\\!\\!&\\!\\!\\!|&|\\!\\!\\!&\\!\\!\\![^{xx}_{02}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{0}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![\emptyset]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{2}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xx}_{20}]\\!\\!\\!&\\!\\!\\!|\\\
00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10&00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\\
|\\!\\!\\!&\\!\\!\\![^{xxy}_{010}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{00}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{0}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{10}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{100}]\\!\\!\\!&\\!\\!\\!|&|\\!\\!\\!&\\!\\!\\![^{xxy}_{020}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{00}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{0}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{20}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{200}]\\!\\!\\!&\\!\\!\\!|\\\
10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11&20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\\
|\\!\\!\\!&\\!\\!\\![^{xxyy}_{0101}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{001}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{yy}_{01}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{101}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{1001}]\\!\\!\\!&|\\!\\!\\!&|\\!\\!\\!&\\!\\!\\![^{xxyy}_{0202}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{002}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{yy}_{02}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{202}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{2002}]\\!\\!\\!&\\!\\!\\!|\\\
00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01&00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\\
\hline\cr\hline\cr
12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22&\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
|\\!\\!\\!&\\!\\!\\![^{xxyy}_{1221}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{121}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{yy}_{21}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{221}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{2121}]\\!\\!\\!&\\!\\!\\!|&\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21&&\\!\\!\\!\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
|\\!\\!\\!&\\!\\!\\![^{xxy}_{122}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{12}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{2}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{22}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{212}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22&&\\!\\!\\!\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!01\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
|\\!\\!\\!&\\!\\!\\![^{xx}_{12}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{1}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![\emptyset]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{x}_{2}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xx}_{21}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![\emptyset]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21&&\\!\\!\\!\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!00\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!10\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!20\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
|\\!\\!\\!&\\!\\!\\![^{xxy}_{121}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{11}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{y}_{1}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{21}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxy}_{211}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22&&\\!\\!\\!\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!02\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!12\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!22\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
|\\!\\!\\!&\\!\\!\\![^{xxyy}_{1212}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{112}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xy}_{12}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xyy}_{212}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\![^{xxyy}_{2112}]\\!\\!\\!&\\!\\!\\!|\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!11\\!\\!\\!&\\!\\!\\!-\\!\\!\\!&\\!\\!\\!21&&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\!\\!\\!&\\!\\!\\!\\\
\hline\cr\hline\cr\end{array}$

This way, six tersquares $[^{x}_{0}],\ldots,[^{y}_{2}]$ are obtained (to be
called subcentral tersquares, colored yellow and light-blue in Figure 2) that
intersect $[\emptyset]$ respectively in the triangles $x^{0},\ldots,y^{2}$.
Next, we glue to the remaining new triangles (i.e., other than those already
in $[\emptyset]$), a set of nine new tersquares that we denote
$[^{xy}_{00}],\ldots,[^{xy}_{22}]$ (and call corner tersquares, colored green
and gray in Figure 2). These nine tersquares share merely a vertex with
$[\emptyset]$ and their disposition with respect to the central tersquare
$[\emptyset]$ and subcentral tersquares $x^{0},\ldots,y^{2}$ is specified in
Figure 2. In fact, $[^{xy}_{ij}]$ shares a triangle $y^{j}$ with $[^{x}_{i}]$
and a triangle $x^{i}$ with $[^{y}_{j}]$, for $i,j=0,1,2$. Such triangles can
be further specified respectively as $y^{j}[^{x}_{i}]$ and $x^{i}[^{y}_{j}]$.

Figure 2: Representing a PDS of $[[\emptyset]]$ in $\Gamma_{2}$

The graph $[[\emptyset]]$ resulting from the union of the $1+6+9=16$
tersquares constructed so far, will be referred to as the 2-hive
$[[\emptyset]]$. The central tersquare $[\emptyset]$ of $[[\emptyset]]$ shares
just one triangle with each of the six subcentral tercubes and just one vertex
with each of the nine corner tersquares. The tersquare $[\emptyset]$, given as
a subgraph at the center of Figure 2, also results in the representation at
the lower-right quarter of Table I by identifying the quadruple of vertices
labelled 22, as well as each pair of vertices labelled 20, 21, 02 and 12.

The construction above continues with the iterative glueing of tersquares
along free triangles, namely those triangles along which glueing of a new
continuing tersquare was not already performed. In the limit of feasible
glueings, a total compound graph$\Gamma_{2}$ of tersquares, glued in pairs of
adjacent tersquares along corresponding triangles, results in an infinite
locally finite graph, the ternary square compound graph $\Gamma_{2}$, that we
also call ternary non-lattice superlattice graph. Notation for all tersquares
and triangles of $\Gamma_{2}$, continuing the notation of the 16 tersquares
and their triangles above, is completed below. The word “superlattice” here
corresponds to the fact that, even though $\Gamma_{2}$ is not a lattice graph
itself, it restricts to lattice graphs when restricted to binary square
compound graphs, as in Remark 1 by puncturing all elements bearing a single
value of $F_{3}$.

Figure 3: Planar projection of a portion of $\Gamma_{2}$ larger than in Figure
2

Three subgraphs of $\Gamma_{2}$ are represented in Table I, containing just
one 4-cycle (of the 9 in $Q_{2}^{3}$) per participating (but not totally
shown) glued tersquare. This yields 9 sub-lattice types in $\Gamma_{2}$ (one
per 4-cycle of $Q_{2}^{3}$, three partially shown in Table I), each isomorphic
to $\Lambda_{2}$. Thus, $\Gamma_{2}$ is a superset of each of the copies of
$\Lambda_{2}$ generated by some 4-cycle of $\Gamma_{2}$. We further specify
$\Gamma_{2}$ after presenting a non-isolated PDS in $[[\emptyset]]$ (Theorem
2.1).

The large connected graph in Figure 2 represents the 2-hive $[[\emptyset]]$,
with $[^{x}_{0}]$, $[^{x}_{1}]$ and $[^{x}_{2}]$ in light-blue background,
$[^{y}_{0}]$, $[^{y}_{1}]$ and $[^{x}_{2}]$ in yellow background, and the nine
tersquares $[^{xy}_{i\,j}]$ in green background if $y\neq 1$ and light-gray
background if $y=1$, where the apparent colored areas spatial disposition
results in the partial hiding of some of these areas. The thick red edges
induce a subgraph of $[[\emptyset]]$ whose vertex set is a non-isolated PDS
$S$ (as defined in Remark 1) of $[[\emptyset]]$. The dominating edges are
drawn in thick black trace, allowing the reader to verify that all vertices of
$[[\emptyset]]$ not in $S$ are dominated as indicated in Remark 1. (It is
elementary to verify that no isolated PDS in $[[\emptyset]]$ exists). The
remaining edges of $[[\emptyset]]$, not in thick trace, are in dashed trace if
they are “exterior” edges of $[[\emptyset]]$ (i.e., those shared by 2-hives
other than $[[\emptyset]]$ in $\Gamma_{2}$) and in thin trace otherwise (i.e.,
if they are “interior” edges of $[[\emptyset]]$). Motivation for pursuing such
a non-isolated PDS arose as a palliative remedy for the impossibility of
having here a PDS like the Livingston-Stout PDS in the grid $P_{4}\square
P_{4}$ [17], which happens to be the only isolated PDS in grid graphs
$P_{m}\square P_{n}$, for $2<min\\{m,n\\}$ [6].

######  Theorem 2.1.

There exists a non-isolated PDS, or
1-PTMC$[Q_{1}^{2},Q_{2}^{2},Q_{1}^{3}\square Q_{1}^{2};4,$ $1,1]$, in the
2-hive $[[\emptyset]]\subset\Gamma_{2}$.

######  Proof 2.2.

The claimed PDS in $[[\emptyset]]$ is formed by the vertex sets of the
following components (of its induced subgraphs):

  1. (a)

the edge $(00,01)$ of triangle $(00,01,02)$ shared by tersquares $[^{y}_{2}]$
and $[^{xy}_{02}]$;

  2. (b)

the edge $(10,20)$ of triangle $(00,10,20)$ shared by tersquares $[^{x}_{0}]$
and $[^{xy}_{00}]$;

  3. (c)

the edge $(21,22)$ of triangle $(20,21,22)$ shared by tersquares $[^{y}_{0}]$
and $[^{xy}_{20}]$;

  4. (d)

the edge $(00,02)$ of triangle $(00,02,01)$ shared by tersquares $[^{y}_{1}]$
and $[^{xy}_{01}]$;

  5. (e)

the 4-cycle $(02,12,11,01)$ of tersquare $[^{x}_{2}]$, where its edge
$(02,12)$ (of triangle $\Delta=(02,12,22)$) is shared (with $\Delta$) with
tersquare $[^{xy}_{22}]$;

  6. (f)

the triangular prism in $[^{x}_{1}]$ formed by triangles $(00,01,02)$ and
$(20,$ $21,22)$ and edges $(00,20)$, $(02,22)$ (of triangle $(02,22,12)$,
shared by tersquare $[^{xy}_{22}]$) and $(01,21)$ (of triangle $(01,21,11)$,
shared by tersquare $[^{xy}_{11}]$).

As can be verified in Figure 2, the edges departing from these red-edge
components cover all other vertices of $[[\emptyset]]$, proving the theorem.

Figure 2 may be augmented by adding the tersquares $[^{xx\,y}_{i\,j\,k}]$,
with $i\neq j$ in $F_{3}$, etc. One may continue by adding tersquares
$[^{xx\cdots xx\,yy\cdots yy}_{i\,j\,\cdots kl\,mn\cdots pq}]$ with $i\neq
j\neq\ldots\neq k\neq l$ (resp. $m\neq n\neq\ldots\neq p\neq q$), i.e. not two
contiguous equal values under the $x$’s (resp. $y$’s). Taking
$i,j,\ldots,k,l,m,n,\ldots p,q$ in $F_{3}$ to be contiguously different with
just two values, (e.g. 0,1; resp. 0,2; resp. 1,2, in the upper-left; resp.
upper-right; resp. lower-left quarter in Table I) is a way of obtaining 3 sub-
lattices of $\Gamma_{2}$, each isomorphic to $\Lambda_{2}$, as in Table I. But
there is an infinite family of “parallel” sub-lattices in $\Gamma_{2}$ for
each of the 9 sublattice types, one per each 4-cycle of a typical tersquare as
in the lower-left quarter of Table I. For example, the type with values 0,2
represents “parallel” sub-lattices having “shortest” tersquares $[\emptyset]$,
$[^{x}_{1}]$, $[^{y}_{1}]$, $[^{xx}_{01}]$, $[^{yy}_{01}]$, $[^{xx}_{21}]$,
$[^{yy}_{21}]$, etc., including every $[^{xx\cdots xx}_{i\,j\,\cdots kl}]$,
$[^{\,y\,y\cdots y\,y}_{mn\cdots pq}]$ and $[^{xx\cdots xx\,\,yy\cdots
yy}_{i\,j\,\cdots kl\,mn\cdots pq}]$.

Figure 4: Components of a 2-PTMC$[Q_{2}^{2}]$ of $[[\emptyset]]$ in
$\Gamma_{2}$

These sub-lattices can be refined by replacing each edge $e$ in them by the
2-path closing a triangle with $e$ and adding more vertices and additional
edges out of them to the new vertices obtained by the said replacement, in
order to distinguish the glued $2$-tercubes in $\Gamma_{2}$. In particular,
Figure 2 is obtained from such a procedure by starting from a plane containing
the upper-right quarter of Table I. Figure 3 shows a projection of a partial
extension of Figure 2 in such a plane, where tersquare colors are kept as in
Figure 2, including if they are projected into a 2-path. Colors here still are
light-blue, blue, green and light-gray. Each tersquare in Figure 3,
represented by four squares with the common central vertex $11$, is just
recognizable by its upper-left vertex denomination presence. Of the four such
squares, the lower-right one has the corresponding tersquare denomination. The
other tersquare denominations in the three remaining squares correspond to the
counterpart denominations in the representation of $[\emptyset]$.

A ternary $n$-cube compound graph $\Gamma_{n}$ is defined as the union of all
necessary $n$-tercubes that appeared glued along their (codimension 1) ternary
$(n-1)$-subtercubes, for any $2<n\in\mathbb{Z}$. The vertices of such
$\Gamma_{n}$ are given in terms of the $n$-tercubes. These, that can be
denoted

$[^{x}_{0}],[^{y}_{0}],\ldots,[^{z}_{0}],[^{x}_{1}],[^{y}_{1}],\ldots,[^{z}_{1}],[^{x}_{2}],[^{y}_{2}],\ldots,[^{z}_{2}],[^{xy}_{00}],\ldots$

including all those of the general form $[J]=[^{xx\cdots xx\,yy\cdots
yy\,\cdots\cdots\cdots\,zz\cdots zz}_{i\,j\,\cdots kl\,mn\cdots
pq\,\cdots\cdots\cdots\,rs\cdots vw}]$, where $x,y,\ldots,z$ represent the $n$
(ternary) coordinate directions. Such $n$-tercubes are assigned locally by
reflection on the $(n-1)$-subtercubes. Thus the said vertices can be denoted
$x^{0}[J],\ldots,z^{2}[J]$, by following the notations above.

Figure 2 for $n=2$, represents the 2-hive $[[\emptyset]]$ with $[\emptyset]$
at its center, and its neighboring tersquares $[^{x}_{0}]$, $[^{x}_{1}]$,
$[^{x}_{2}]$ in light-blue background, $[^{y}_{0}]$, and $[^{y}_{1}]$,
$[^{y}_{2}]$ in yellow background, and the tersquares neighboring those
tersquares, namely $[^{xy}_{i\,j}]$, ($i,j\in F_{3}$), in green and light-gray
backgrounds. It can be seen that $\Gamma_{n}$ may be considered as a superset
of $\Lambda_{n}$ in three different ways, as was commented above in relation
to Table I for $n=2$.

We pose the following.

Phys. Rev. B Does there exist a non-isolated PDS $S$ in $\Gamma_{n}$, for
$n\geq 2$? If so, could $S$ behave like a lattice, for example by restricting
itself to a lattice PDS over any sub-lattice of $\Gamma_{n}$, as exemplified
in Table I?

##  3 Isolated 2-PTMC’s in $\Gamma_{2}$

In this section, we keep working in $\Gamma_{2}$, but slightly modifying the
definition of a $\kappa$-PTMC by replacing the used Hamming distance $h$ by
the graph distance of $\Gamma_{2}$. It is clear that the Hamming distance in
our graph-theoretical context is just the graph distance. Then, we have the
following result.

######  Theorem 3.1.

There exists 262144 isolated 2-PTMC’s in the 2-hive
$[[\emptyset]]\subset\Gamma_{2}$.

######  Proof 3.2.

In Figure 4, the nine copies $[^{xy}_{ij}]$, ($i,j\in F_{3}$), of the
tersquare are shown with its edges in thick black trace, against the thin
black trace of the remaining edges of the 2-hive $[[\emptyset]]$. These nine
copies happen to be the truncated 2-spheres centered at the vertices of an
isolated PTMC of $[[\emptyset]]$ constituted as a selection of one vertex per
yellow-faced 4-cycle in the figure. We may say that these yellow-faced
4-cycles are the ”external” 4-cycles of $[[\emptyset]]$. So, there are
$4^{9}=262144$ 2-PTMC’s in $\Gamma_{2}$.

Figure 5: Analysis of the square $(00,01,11,10)$ in tersquare $[^{xy}_{22}]$

.

######  Corollary 9.

There exists a 2-PTMC$[Q_{2}^{2}]$ in the 2-hive $[[\emptyset]]$.

######  Proof 3.3.

The yellow-faced 4-cycles are copies of $Q_{2}^{2}$ and induce the components
of the claimed 2–PTMC-$[Q_{2}^{2}]$.

######  Theorem 3.4.

There exists an infinite number of isolated 2-PTMC in $\Gamma_{2}$.

######  Proof 3.5.

Let us analyze one of the yellow squares in Figure 4, say square (00,
01,11,10) in tersquare $[^{xy}_{22}]$ , as represented in Figure 5; the
remaining eight yellow squares have similar properties to those to be
described, once the notations of local vertices and neighboring tercubes are
updated in each case in place of those in the figure. Besides the “external”
4-cycle $(00,01,11,10)$ in Figure 5, whose edges are in black color, we set in
red and blue, (green and hazel) colors those additional edges defining a pair
of 4-cycles in the respective tercubes $[^{xxy}_{202}]$ and $[^{xxy}_{212}]$,
($[^{xyy}_{220}]$ and $[^{xyy}_{221}]$), namely
$\\{(00,02,12,10),(01,02,12,11)\\}$, ($\\{(00,20,21,01),(10,20,21,11)\\}$),
equally denoted but pertaining to different tersquares, as shown. Since it is
seen that the maximum truncated distance in Figure 5 is 2, we conclude that
any one of the four vertices of the black 4-cycle dominates the remaining
vertices in the other 4-cycles in the figure, in positions in their tersquares
similar to those of the yellow cycles in Figure 4, namely the four just
mentioned tersquares as well as the “opposite” tersquares
$[^{xxyy}_{2020}]$,$[^{xxyy}_{2021}]$, $[^{xxyy}_{2120}]$ and
$[^{xxyy}_{2121}]$, where these involved tersquare denominations are set in
Figure 5 straddling edges common to two of their 4-cycles, for better
reference, twice for the last four mentioned tersquares. This particular case
is easily generalized to conclude that each vertex in a yellow square
dominates via $\rho$ in the neighboring tersquares in a form similar to that
of $[[\emptyset]]$.

With the same structure as the 2-hive $[[\emptyset]]$, we have the 2-hives of
its neighboring 2-hive pair $\\{[[^{xxx}_{010}]],[[^{xxx}_{012}]]\\}$, etc.,
sharing four tersquares with $[[\emptyset]]$, tersquares denoted $(10,11,12)$
, both in $[^{x}_{0}]$ and in $[^{xy}_{00}]$ and $[^{xy}_{01}]$ and
$[^{xy}_{02}]$. These four tersquares belong both in $[[^{xxx}_{010}]]$ and
$[[^{xxx}_{012}]]$ to the four respective tercubes $[^{xx}_{01}]$,
$[^{xxy}_{010}]$, $[^{xxy}_{011}]$ and $[^{xxy}_{012}]$. Moreover, the union
of these four tercubes constitutes the intersection
$[[^{xxx}_{010}]]\cap[[^{xxx}_{012}]]$. By considering in each of these two
2-hives the equivalent of the yellow squares of $[[\emptyset]]$ in Figure 4,
and selecting in each such yellow square a vertex contributing to the
construction of an isolated 2-PTMC of $\Gamma_{2}$,, iteration of such a
procedure eventually allows the completion of such dominating set. Observe
that the argument exposed from the 2-hive pair
$\\{[[^{xxx}_{010}]],[[^{xxx}_{012}]]\\}$ is one of twelve cases arising from
the 2-hive $[[\emptyset]]$. Iteration of these twelve cases departing from any
2-hive of $\Gamma_{2}$ that is reached in the continuing procedure allows to
advance a further step in the construction of such isolated 2-PTMC.

######  Remark 10.

The argument of Theorem 3.4 can be modified to ascertain the existence of
2-PTMC$[H]$, where $H$ is a 4-cycle, or the union of yellow squares with a
common vertex in different 2-hives, like the eight squares, in Figure 5, at
vertex 10 in the tersquares $[^{xy}_{2,2}]$, $[^{xxy}_{202}]$.
$[^{xxy}_{212}]$, $[^{xyy}_{220}]$, $[^{xyy}_{221}]$, $[^{xxyy}_{2020}]$,
${}^{xxyy}_{2021}]$ and $[^{xxyy}_{2120}]$.

There exists an isolated $n$-PTMC in $\Gamma_{n}$, $\forall n>2$.

Phys. Rev. B Does there exist a suitable way of declaring a susbset $S\subset
V(\Gamma_{n})$ to be periodic, or periodic-like, that extends the notion of
periodicity of $\Lambda_{n}$ at the end of Remark 6 to one in $\Gamma_{n}$? so
that a replacement of the notion of “quotient” or “toroidal” graphs of
$\Lambda_{n}$ can be found that way for $\Gamma_{n}$?

##  4 Appendix

On the left of Figure 6, an oriented representation of a ternary square is
provided. Here, one may take the vertices as decision conditional diamonds,
the outgoing arrows as “Yes” or “True” option arrows and the incoming arrows
as “No” or “False” option arrows. An elementary flowchart modeled on this
oriented ternary square is given as an example on the right of Figure 6, where
the root of the flowchart corresponds to vertex 00 and there are four
terminators, corresponding to the vertices 01, 02, 11 and 12. The decision
conditional diamonds correspond to the vertices 00, 10, 20, 21 and 22. To
avoid terminators that are the end of more than one process, as is the case of
11 and 12 in the figure, one may select in $\Gamma_{2}$ modeling flowchart
continuation in adjacent tercubes to the immediately previous ones, each
sharing with the current tercube an already used triangle.

Figure 6: Ternary square as a model of algorithm flowchart

Acknowledgement: We thank the two anonymous reviewers that provided helpful
comments on an earlier draft of this manuscript.

## References

  * [1] C. Araujo, I. Dejter and P. Horak, A generalization of Lee codes, Designs, Codes and Cryptography, 70 (2014), 77–90.
  * [2] S. Buzaglo and T. Etzion, Tilings by $(0.5,n)$-Crosses and Perfect Codes., SIAM Jour. Discrete Math., 27 (2013), 1067–1081.
  * [3] R. Calderbank, ed., Different aspects of coding theory: AMS Short Course, San Francisco, CA, AMS, Proc. Symp. Appl. Math., 50 1995\.
  * [4] A. Campello, G. C. Jorge, J. E. Strapasson, S. I. R. Costa, Perfect codes in the $\ell_{p}$ distance, European Journal of Combinatorics, 53 (2016),72–85.
  * [5] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering codes, Elsevier 1997.
  * [6] I. Dejter, A. Delgado, Perfect dominating sets in rectangular grid graphs, J. Combin. Math. Combin. Comput., 70 (2009), 177–196.
  * [7] I. Dejter, L. Fuentes and C. Araujo, There is but one PDS in $\mathbb{Z}^{3}$ inducing just square components, Bull. Inst. Combin. Appl., 82 (2018), 30–41.
  * [8] I. Dejter and O. Serra, Efficient dominating sets in Cayley graphs, Discrete Applied Mathematics, 129 (2003), 319–328.
  * [9] I. Dejter and P. Weichsel, Twisted perfect dominating subgraphs of hypercubes, Congr. Numer. 94 (1993), 67–78.
  * [10] T. Etzion, Product constructions for perfect Lee codes, IEEE Transactions in Information Theory, 57 (2011), 7473–7481.
  * [11] T. Etzion, Tilings with generalized Lee spheres, in: J.-S. No et al., eds., Mathematical Properties of Sequences, Springer 726 (2003), 181–198.
  * [12] L. Fuentes, I. Dejter and C. Araujo, Rainbow perfect domination in lattice graphs, Electronic Journal Graph Theory and Applications, 6 (1) (2018), 95–112
  * [13] S. Golomb and K. Welch, Perfect codes in the Lee metric and the packing of polyominoes, SIAM Jour. Applied Math., 18 (1970), 302–317.
  * [14] P. Horak and B. F. AlBdaiwi, Diameter perfect Lee codes, IEEE Transactions of Information Theory, 58 (2012),5490–5499.
  * [15] P. Horak and O. Grosek, A new approach towards the Golomb-Welch conjecture. European Journal of Combinatorics, 38 (2014), 12–22.
  * [16] P. Horak and D. Kim, 50 Years of the Golomb-Welch Conjecture, IEEE Transactions on Information Theory, 60 (2018), 3048–3061.
  * [17] M. Livingston and Q. F. Stout, Perfect Dominating Sets, Congr. Numer., 79 (1990), 187–203.
  * [18] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier 1977.
  * [19] P. Östergård and W. Weakley, Constructing covering codes with given automorphism, Designs, Codes and Cryptography, 16 (1999), 65–73.
  * [20] P. M. Weichsel, Dominating sets in $n$-cubes, Journal of Graph Theory, 18 (1994) 479–488.