关于递归替换最内层4-环为立方体的四边形剖分的命名及简洁表示的问询
Hey there! Great question about these recursively built quadrangulations—they’re a neat class of planar graphs, so let’s break down what I know:
命名
First off, there isn’t a single universal name everyone uses, but here are some common terms you’ll encounter in combinatorial graph theory contexts:
- Recursively cube-augmented 4-connected planar quadrangulations: This emphasizes both the recursive cube-adding construction and the core property of being 4-connected planar graphs with all faces as 4-cycles.
- Inner-face cube-substituted quadrangulations: This highlights the key operation—replacing innermost 4-cycles (inner faces) with planar cube embeddings.
- Hierarchically cubulated quadrangulations: If you’re focusing on the layered, recursive structure, this term fits well too.
These graphs also fall under the broader umbrella of 4-regular planar quadrangulations (after the first substitution step, every vertex has a degree of 4).
简洁表示
You can describe this class formally with a recursive definition, or use combinatorial formulas to track their size at each recursion step:
递归构造定义
- Base case: Let $Q_0$ be a simple 4-cycle (denoted $C_4$—4 vertices connected in a loop).
- Recursive step: For any $n \geq 0$, $Q_{n+1}$ is formed by taking every innermost 4-face in $Q_n$ and replacing it with a planar embedding of a cube. Specifically, the original 4-cycle becomes one face of the cube, and we add 4 new vertices inside the original face to form the cube’s remaining 5 faces—with the innermost of these new faces being a fresh 4-cycle ready for the next substitution.
组合计数公式
If you want to quantify the graph’s size at each recursion step, these recurrence formulas work:
- 顶点数: $V_0 = 4$, $V_{n+1} = V_n + 4$ (each substitution adds 4 new vertices) → $V_n = 4(n + 1)$
- 边数: $E_0 = 4$, $E_{n+1} = E_n + 8$ (each substitution replaces 4 old edges with 12 cube edges, net +8) → $E_n = 4 + 8n$
- 面数: $F_0 = 2$, $F_{n+1} = F_n + 4$ (each substitution turns 1 inner face into 5 new faces, net +4) → $F_n = 2 + 4n$
You can also use a shorthand operator to describe the construction: let $\text{CubeSub}(G)$ represent the graph formed by applying the cube substitution to all innermost 4-faces of $G$. Then $Q_n = \text{CubeSub}^n(C_4)$, where the superscript denotes applying the operation $n$ times.
Hope this gives you a clear framework for talking about these graphs!
备注：内容来源于stack exchange，提问作者licheng
