graph - 如何创建一个特殊的图表？

Question

我希望生成具有以下特征的无向晶格图G ：

1. 它有m x n 个顶点；
2. 每个顶点只有两种标签（0 或 1）；
3. 每个t x t子图都是唯一的。

例如，如果格图G的顶点标签的数组是

1 1 1 1 0
0 1 0 0 1
1 0 0 1 1
1 1 0 0 0
1 1 0 0 1

那么G的任何 3x3 子图都是唯一的（只能找到一个同构）。例如，子图

1 0 1
0 1 1
0 0 1

只能是G的左上角块，旋转 90 度。

---

实际上，我可以通过波函数折叠来生成这样的图表。上面的例子就是这样生成的。

但是，我想更进一步。以下是真正的问题：

1. 如果子图可以是任何形状（至少有t个顶点），如何生成图G？
2. 如果图G的格子形状不受限制，会发生什么？
3. 子图的形状与使它们唯一的最小顶点数t之间的关系是什么？

任何想法或关键字？

标签： graphuniquelatticesubgraph