多面体图按公共邻居数的分类

《Discrete Applied Mathematics》:Classification of polyhedral graphs by numbers of common neighbours

【字体: 大 中 小 】 时间:2026年09月23日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   ## 摘要 我们提出了一种多面体(即平面、3-连通图)的分类方法,按类型进行分类,其中"类型"是指对于每对不同顶点,其公共邻居数量所构成的集合。 对于任意(有限)非负整数集合,我们要么完整分类该类型的所有多面体,要么构造该类型的无穷多个多面体,要么证明不存在该类型的多面体

  

## 摘要

我们提出了一种多面体(即平面、3-连通图)的分类方法,按类型进行分类,其中"类型"是指对于每对不同顶点,其公共邻居数量所构成的集合。

对于任意(有限)非负整数集合,我们要么完整分类该类型的所有多面体,要么构造该类型的无穷多个多面体,要么证明不存在该类型的多面体。

该问题与强正则图和Deza图理论、图中的距离概念以及度序列相关。在复杂网络和数据科学领域具有潜在的应用价值。

## 引言

本文研究有限、无向图 $G=(V,E)$,其中没有重边和自环。我们用 $N(u)$ 表示 $u\in V(G)$ 的邻居集合(即与 $u$ 相邻的顶点集合),用 $N(u,v)$ 表示顶点 $u$ 和 $v$ 的公共邻居集合。

多面体(也称为3-多面体)是平面、3-连通的图。同构意义下的多面体图与同胚意义下的多面体固体之间存在自然的对应关系。多面体图在球面上有唯一的嵌入方式[16],因此通过球极投影也可以在平面上唯一嵌入(一旦选定外部区域)。因此,我们始终考虑多面体及其在平面上的嵌入。关于多面体图的更多细节和性质,参见文献[8]的引言部分。

正则图被称为强正则图,如果存在非负整数 $\lambda, \mu$,使得每对相邻顶点有 $\lambda$ 个公共邻居,且每对不相邻顶点有 $\mu$ 个公共邻居。正则图被称为Deza图,如果存在非负整数 $\lambda, \mu$,使得每对顶点有 $\lambda$ 或 $\mu$ 个公共邻居。因此,Deza图是强正则图的推广。等价地,正则图 $G$ 是Deza图当且仅当 $|A|\leq 2$,其中 $A=A(G):=\{a:\exists u,v\in V(G)\text{ 使得 } |N(u,v)|=a\}$。

在文献[10, 命题1.1]中可以找到所有平面Deza图的分类。关于Deza图理论,请参考奠基性论文[2],以及后续文献[3]、[5]。该领域最著名且引人注目的未解决问题之一可能是"缺失的Moore图"[1]。

在图论的应用中,例如复杂网络和数据科学领域,公共邻居数量已作为顶点相似度的度量被广泛研究[7]、[11]、[13]、[14]、[15]、[17]。关于相关的邻域复杂度概念,参见[12],特别是平面图的相关讨论见[6]。

我们称图 $G$ 的类型为 $\mathbf{A}$,如果 $A=A(G)$。也就是说,本文将使用"类型"作为"每对不同顶点的公共邻居数量集合"这一概念的缩写。在文献[10, 定理1.2]中,我们已按照类型对所有正则多面体进行了分类。除少数特殊情况外,对于正则多面体 $G$,集合 $A$ 是 $\{0,1\}$、$\{0,1,2\}$、$\{0,1,2,3\}$、$\{0,1,2,4\}$、$\{0,1,2,3,4\}$ 之一。

对于任何图(无论是否为正则图),都可以定义集合 $A$。在本文中,我们提出一个更丰富的问题:按类型对所有多面体进行分类,从而推广了文献[10, 定理1.2]。对于每个有限的非负整数集合 $A$,我们要么刻画所有满足 $A=A(G)$ 的无穷多个或有限多个解 $G$,要么构造一类满足 $A=A(G)$ 的多面体 $G$,要么证明不存在这样的多面体。为了详细描述我们的结果,我们需要首先定义若干多面体类。

令 $T_\ell = P_\ell + K_2$,如图1所示,其中 $P_\ell$ 是 $\ell$ 个顶点的路径,$+$ 是图的并运算。注意 $T_1$ 是三角形,$T_2$ 是四面体,$T_3$ 是三角双锥体。对于 $\ell\geq 2$,$T_\ell$ 是多面体。

我们定义多面体族 $\mathfrak{S}_1 := \{\text{双锥体}\}\cup\{T_\ell: \ell\geq 2\}\cup\{S_i: 1\leq i\leq 10\}$,

其中 $S_1, S_2, \ldots, S_{10}$ 是图2中的图。注意八面体是正方双锥体。

**定义1.1**

我们将 $\mathcal{W}_3$ 称为从 $n$ 角锥体(即轮图),$n\geq 5$,出发,添加若干条两两独立的边(至少一条)所得到的多面体类。

我们将 $\mathcal{W}_4$ 称为多面体 $G$ 的类,其中 $G$ 是从底面为 $[v_1, v_2, \ldots, v_n]$、$n\geq 5$ 的锥体出发,添加两两不相交的圈(至少一个)所得到的,且满足以下所有条件:每个圈的长度不等于4;如果某个圈的长度为3,且 $v_i, v_j$($i
$\mathcal{w}_3$ 的一个成员出现在图3中。

**定义1.2**

令 $n\geq 4$ 为偶数。我们定义图 $b_n$:从圈 $b_1, b_2, \ldots, b_{2n}$ 出发,添加边 $xb_i$($1\leq i\leq 2n$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n$)。

我们还定义图 $b'_n$:从路径 $b_1, b_2, \ldots, b_{2n-2}$ 出发,添加边 $xb_i$($1\leq i\leq 2n-2$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n-2$)。

示意图见图4。这些图族满足 $a(b_n)=a(b'_n)=\{1,2,n\}$。注意所定义的图是多面体,且 $b_n-y$ 同构于 $2n$ 角锥体。

现在我们准备陈述主要结果。

**定理1.3** 多面体 $g$ 满足 $1\notin a$ 当且仅当 $g\in\mathfrak{s}_1$。分类结果见表1。

定理1.3将在第2节中证明。

**定理1.4** 设 $g$ 是阶为 $p$ 的多面体,满足 $1\in a$,且 $a'_n$ 是 $\geq n$ 的整数的(有限)非空集合。则 $g$ 属于表2第一列所列的某一类型,对应的条件如第二列所述。

定理1.3和定理1.4共同完整地分类了所有多面体的类型。定理1.4将在第3、4、5、6节中证明,通过呈现中间结果来填充表2。

对于类型 $\{1,2\}$、$\{1,2,3\}$、$\{1,2,4\}$ 和 $\{1,2,\ell\}$($\ell\geq 6$ 为偶数),在第4节"图半径为1的多面体"和第5节"多面体类型分类的完成"中,我们将证明除有限个解外,其余所有解要么是锥体,要么属于 $\mathcal{w}_3$、$\mathcal{w}_4$、$b_\ell$、$b'_\ell$ 之一。

对于表2中其余的每个类型 $\{0,1\}$、$\{0,1,2\}$、$\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$,均存在该类型的广泛多面体类。对于类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的情况,文献[10]中已有所展示。例如,有以下显式类:所有围长(即最小面长度)为5的多面体均满足 $a=\{0,1\}$。除立方体外,所有包含四边形面的3-正则(即立方)多面体均满足 $a=\{0,1,2\}$[10, 定理1.2]。

本文将大大加强类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的结果。在第3节中,我们将证明多面体满足 $a=\{0,1\}$ 当且仅当它不包含4-圈。在第4节中,我们将给出至少25个顶点的多面体满足 $a=\{0,1,2\}$ 的充要条件。

在第6节中,对于类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个,我们将构造相应类型的广泛多面体类。对于所有不出现在表1和表2中的非负整数集合 $a$,我们将在第5节中证明不存在满足 $a=a(g)$ 的多面体 $g$。

若一个图至少有 $k+1$ 个顶点,且无论移除其中少于 $k$ 个顶点,所得图仍连通,则称该图为 $k$-连通的。

若一个图可以嵌入到平面中且边仅在顶点处相交,则称该图为平面图的。平面图是平面图的及其一种平面嵌入。多面体图的嵌入在选定外部区域后是唯一的,因此我们默认将它们连同其嵌入一起考虑。

若一个平面图存在一种平面嵌入使得所有顶点都在某一个区域的边界上,则称该图为外平面图的。

对于(非平凡的)连通图 $g$,顶点 $u$ 的离心率 $\text{ecc}(u)$ 是 $u$ 到 $v\in v(g)$ 的最大距离。所有顶点中最大的离心率是 $g$ 的直径 $\text{diam}(g)$。等价地,$\text{diam}(g)$ 是 $g$ 中任意一对顶点之间的最大距离。$g$ 的半径 $\text{rad}(g)$ 是最小的顶点离心率。众所周知,对于任何连通图 $g$,$\text{rad}(g)\leq \text{diam}(g)\leq 2\text{rad}(g)$。

图的直径为1当且仅当它是完全图。图的半径为1当且仅当存在一个顶点与所有其他顶点相邻,也称为支配顶点。

给定平面图 $g$ 和 $u\in v(g)$,我们定义 $u$ 在 $g$ 中的平面邻域为 $g$ 的子图 $\gamma_u(g)$,其中 $e(\gamma_u(g))=\{e\in e(g): e \text{ 位于包含 } u \text{ 的某个区域上}\}$。

符号 $a'_n$ 各处表示 $\geq n$ 的整数的有限非空集合。

第2节完全用于证明定理1.3。接下来的四节用于证明定理1.4。在第3节中,我们将给出预备工作。在第4节中,我们将重点关注图半径为1的多面体这一重要类,这在后续工作中将是有用的。在第5节中,我们将完成表2中所述的多面体类型分类。在第6节中,我们将为表2中的若干类型构造广泛的多面体类。这些构造的代码见附录。用于证明定理1.4的结果将在第6节末尾进行总结。

---

## 章节节选

### $1\notin a$ 的多面体类型:定理1.3的证明

设 $1\nnotin a$。我们的第一个目标是证明 $g$ 要么是立方体,要么是球面的三角剖分(极大平面图)。反设 $g$ 包含一个面 $[u_1, u_2, \ldots, u_n]$,$n\geq 5$。

令 $u_{n+1}:=u_1$,$u_{n+2}:=u_2$。由于 $1\notin a$,则对于每个 $1\leq i\leq n$,顶点 $u_i$ 和 $u_{i+2}$ 有一个不同于 $u_{i+1}$ 的公共邻居。由平面性,唯一可能是存在 $v\in v(g)$ 与 $u_1, u_2, \ldots, u_n$ 中每一个都相邻。此外,对于每个 $1\leq i\leq n$,顶点 $u_i, u_{i+1}$ 有一个公共邻居 $w_i\neq v$。

接下来,对于每个 $1\leq i\leq n$,……

### $1\in a$ 情形的预备知识

本文余下部分的最终目标是证明定理1.4。在本节中,我们将建立一些关于一般图 $g$ 的 $a(g)$ 的辅助引理。

**引理3.1** 设 $g$ 是平面图。若存在 $a\geq 3$ 使得 $a\in a$,则 $2\in a$。

**证明** 设 $a\geq 3$ 使得 $a\in a$,并反设 $2\notin a$。我们声称 $g$ 包含一个同构于方锥体的子图。由假设,存在不同的 $u, v\in v(g)$ 使得 $n(u,v)\supseteq\{w_1, w_2, w_3\}$。由于 $2\notin a$,则 $w_1, w_2$ 有一个公共邻居 $x\notin\{u, v\}$,……

### 图半径为1的多面体

在本节及后续节中,我们将开始填充表2。我们需要一些关于图半径为1的多面体的辅助结果,这些结果在我们的论证中起着核心作用。

**引理4.1** 给定图半径为1的多面体 $g\not\simeq t_\ell$,$g$ 中恰有一个离心率为1的顶点。

**证明** 记图中离心率为1的顶点个数为 $i$。由定义,离心率为1的顶点与所有其他顶点相邻。若 $i\geq 4$,由平面性 $k_5$ 不是 $g$ 的子图,则 $i=4$ 且 $|v(g)|-$……

### 多面体类型分类的完成

本节的目的是证明表2第一列中 $1\in a$ 的多面体类型列表是完备的。为此,我们需要最后一个关键结果:分类所有满足 $0,3,4\notin a$ 且存在 $\ell\in a$($\ell\geq 5$)的多面体。

**命题5.1** 设 $g$ 是多面体图。$0,3,4\notin a$ 且 $\ell\in a$($\ell\geq 5$)当且仅当 $g\simeq b_\ell$ 或 $g\simeq b'_\ell$,其中 $\ell$ 为偶数。

**证明** 设 $\ell$ 是满足 $\ell\geq 5$ 且 $\ell\in a$ 的最小值,$x,y\in v(g)$ 使得 $|n(x,y)|=\ell$。设 $w_1, w_2, \ldots, w_\ell$ 为 $x, y$ 的公共邻居,……

### 广泛的解类

为了完成定理1.3的证明,我们还需为类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个构造无穷多个多面体,其中 $a'_n$ 是 $\geq n$ 的整数的有限非空集合。

**命题6.1** 对于任意(有限)非空整数集合 $a'_4$($\geq 4$),存在无穷多个多面体 $g$ 满足 $a(g)=\{1,2,3\}\cup a'_4$。

**证明** 毛毛虫树 $t$ 是一种树图,删除度为1的顶点后得到一条简单路径($t$ 的"中心路径")。毛毛虫树 $t$ 的度序列由……

## 致谢

riccardo w. maffucci 的部分工作得到"rita levi montalcini"青年研究者项目 pgr21dpcwz "数学及其应用中离散与概率方法"的支持,该项目授予 riccardo w. maffucci。作者感谢两位匿名审稿人提出的宝贵修改建议。

riccardo w. maffucci $v_{i+1}v_{j-1}\notin e(g)$。 $\mathcal{w}_3$ 的一个成员出现在图3中。 **定义1.2** 令 $n\geq 4$ 为偶数。我们定义图 $b_n$:从圈 $b_1, b_2, \ldots, b_{2n}$ 出发,添加边 $xb_i$($1\leq i\leq 2n$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n$)。 我们还定义图 $b'_n$:从路径 $b_1, b_2, \ldots, b_{2n-2}$ 出发,添加边 $xb_i$($1\leq i\leq 2n-2$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n-2$)。 示意图见图4。这些图族满足 $a(b_n)=A(B'_n)=\{1,2,n\}$。注意所定义的图是多面体,且 $b_n-y$ 同构于 $2n$ 角锥体。 现在我们准备陈述主要结果。 **定理1.3** 多面体 $g$ 满足 $1\notin a$ 当且仅当 $g\in\mathfrak{s}_1$。分类结果见表1。 定理1.3将在第2节中证明。 **定理1.4** 设 $g$ 是阶为 $p$ 的多面体,满足 $1\in a$,且 $a'_n$ 是 $\geq n$ 的整数的(有限)非空集合。则 $g$ 属于表2第一列所列的某一类型,对应的条件如第二列所述。 定理1.3和定理1.4共同完整地分类了所有多面体的类型。定理1.4将在第3、4、5、6节中证明,通过呈现中间结果来填充表2。 对于类型 $\{1,2\}$、$\{1,2,3\}$、$\{1,2,4\}$ 和 $\{1,2,\ell\}$($\ell\geq 6$ 为偶数),在第4节"图半径为1的多面体"和第5节"多面体类型分类的完成"中,我们将证明除有限个解外,其余所有解要么是锥体,要么属于 $\mathcal{w}_3$、$\mathcal{w}_4$、$b_\ell$、$b'_\ell$ 之一。 对于表2中其余的每个类型 $\{0,1\}$、$\{0,1,2\}$、$\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$,均存在该类型的广泛多面体类。对于类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的情况,文献[10]中已有所展示。例如,有以下显式类:所有围长(即最小面长度)为5的多面体均满足 $a=\{0,1\}$。除立方体外,所有包含四边形面的3-正则(即立方)多面体均满足 $a=\{0,1,2\}$[10, 定理1.2]。 本文将大大加强类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的结果。在第3节中,我们将证明多面体满足 $a=\{0,1\}$ 当且仅当它不包含4-圈。在第4节中,我们将给出至少25个顶点的多面体满足 $a=\{0,1,2\}$ 的充要条件。 在第6节中,对于类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个,我们将构造相应类型的广泛多面体类。对于所有不出现在表1和表2中的非负整数集合 $a$,我们将在第5节中证明不存在满足 $a=A(G)$ 的多面体 $g$。 若一个图至少有 $k+1$ 个顶点,且无论移除其中少于 $k$ 个顶点,所得图仍连通,则称该图为 $k$-连通的。 若一个图可以嵌入到平面中且边仅在顶点处相交,则称该图为平面图的。平面图是平面图的及其一种平面嵌入。多面体图的嵌入在选定外部区域后是唯一的,因此我们默认将它们连同其嵌入一起考虑。 若一个平面图存在一种平面嵌入使得所有顶点都在某一个区域的边界上,则称该图为外平面图的。 对于(非平凡的)连通图 $g$,顶点 $u$ 的离心率 $\text{ecc}(u)$ 是 $u$ 到 $v\in v(g)$ 的最大距离。所有顶点中最大的离心率是 $g$ 的直径 $\text{diam}(g)$。等价地,$\text{diam}(g)$ 是 $g$ 中任意一对顶点之间的最大距离。$g$ 的半径 $\text{rad}(g)$ 是最小的顶点离心率。众所周知,对于任何连通图 $g$,$\text{rad}(g)\leq \text{diam}(g)\leq 2\text{rad}(g)$。 图的直径为1当且仅当它是完全图。图的半径为1当且仅当存在一个顶点与所有其他顶点相邻,也称为支配顶点。 给定平面图 $g$ 和 $u\in v(g)$,我们定义 $u$ 在 $g$ 中的平面邻域为 $g$ 的子图 $\gamma_u(g)$,其中 $e(\gamma_u(g))=\{e\in e(g): e \text{ 位于包含 } u \text{ 的某个区域上}\}$。 符号 $a'_n$ 各处表示 $\geq n$ 的整数的有限非空集合。 第2节完全用于证明定理1.3。接下来的四节用于证明定理1.4。在第3节中,我们将给出预备工作。在第4节中,我们将重点关注图半径为1的多面体这一重要类,这在后续工作中将是有用的。在第5节中,我们将完成表2中所述的多面体类型分类。在第6节中,我们将为表2中的若干类型构造广泛的多面体类。这些构造的代码见附录。用于证明定理1.4的结果将在第6节末尾进行总结。 --- ## 章节节选 ### $1\notin a$ 的多面体类型:定理1.3的证明 设 $1\nnotin a$。我们的第一个目标是证明 $g$ 要么是立方体,要么是球面的三角剖分(极大平面图)。反设 $g$ 包含一个面 $[u_1, u_2, \ldots, u_n]$,$n\geq 5$。 令 $u_{n+1}:=u_1$,$u_{n+2}:=u_2$。由于 $1\notin a$,则对于每个 $1\leq i\leq n$,顶点 $u_i$ 和 $u_{i+2}$ 有一个不同于 $u_{i+1}$ 的公共邻居。由平面性,唯一可能是存在 $v\in v(g)$ 与 $u_1, u_2, \ldots, u_n$ 中每一个都相邻。此外,对于每个 $1\leq i\leq n$,顶点 $u_i, u_{i+1}$ 有一个公共邻居 $w_i\neq v$。 接下来,对于每个 $1\leq i\leq n$,…… ### $1\in a$ 情形的预备知识 本文余下部分的最终目标是证明定理1.4。在本节中,我们将建立一些关于一般图 $g$ 的 $a(g)$ 的辅助引理。 **引理3.1** 设 $g$ 是平面图。若存在 $a\geq 3$ 使得 $a\in a$,则 $2\in a$。 **证明** 设 $a\geq 3$ 使得 $a\in a$,并反设 $2\notin a$。我们声称 $g$ 包含一个同构于方锥体的子图。由假设,存在不同的 $u, v\in v(g)$ 使得 $n(u,v)\supseteq\{w_1, w_2, w_3\}$。由于 $2\notin a$,则 $w_1, w_2$ 有一个公共邻居 $x\notin\{u, v\}$,…… ### 图半径为1的多面体 在本节及后续节中,我们将开始填充表2。我们需要一些关于图半径为1的多面体的辅助结果,这些结果在我们的论证中起着核心作用。 **引理4.1** 给定图半径为1的多面体 $g\not\simeq t_\ell$,$g$ 中恰有一个离心率为1的顶点。 **证明** 记图中离心率为1的顶点个数为 $i$。由定义,离心率为1的顶点与所有其他顶点相邻。若 $i\geq 4$,由平面性 $k_5$ 不是 $g$ 的子图,则 $i=4$ 且 $|v(g)|-$…… ### 多面体类型分类的完成 本节的目的是证明表2第一列中 $1\in a$ 的多面体类型列表是完备的。为此,我们需要最后一个关键结果:分类所有满足 $0,3,4\notin a$ 且存在 $\ell\in a$($\ell\geq 5$)的多面体。 **命题5.1** 设 $g$ 是多面体图。$0,3,4\notin a$ 且 $\ell\in a$($\ell\geq 5$)当且仅当 $g\simeq b_\ell$ 或 $g\simeq b'_\ell$,其中 $\ell$ 为偶数。 **证明** 设 $\ell$ 是满足 $\ell\geq 5$ 且 $\ell\in a$ 的最小值,$x,y\in v(g)$ 使得 $|n(x,y)|=\ell$。设 $w_1, w_2, \ldots, w_\ell$ 为 $x, y$ 的公共邻居,…… ### 广泛的解类 为了完成定理1.3的证明,我们还需为类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个构造无穷多个多面体,其中 $a'_n$ 是 $\geq n$ 的整数的有限非空集合。 **命题6.1** 对于任意(有限)非空整数集合 $a'_4$($\geq 4$),存在无穷多个多面体 $g$ 满足 $a(g)=\{1,2,3\}\cup a'_4$。 **证明** 毛毛虫树 $t$ 是一种树图,删除度为1的顶点后得到一条简单路径($t$ 的"中心路径")。毛毛虫树 $t$ 的度序列由…… ## 致谢 riccardo w. maffucci 的部分工作得到"rita levi montalcini"青年研究者项目 pgr21dpcwz "数学及其应用中离散与概率方法"的支持,该项目授予 riccardo w. maffucci。作者感谢两位匿名审稿人提出的宝贵修改建议。 riccardo w.>

$\mathcal{w}_3$ 的一个成员出现在图3中。

**定义1.2**

令 $n\geq 4$ 为偶数。我们定义图 $b_n$:从圈 $b_1, b_2, \ldots, b_{2n}$ 出发,添加边 $xb_i$($1\leq i\leq 2n$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n$)。

我们还定义图 $b'_n$:从路径 $b_1, b_2, \ldots, b_{2n-2}$ 出发,添加边 $xb_i$($1\leq i\leq 2n-2$)和 $yb_j$($j\equiv 1,2 \pmod{4}$,$1\leq j\leq 2n-2$)。

示意图见图4。这些图族满足 $a(b_n)=a(b'_n)=\{1,2,n\}$。注意所定义的图是多面体,且 $b_n-y$ 同构于 $2n$ 角锥体。

现在我们准备陈述主要结果。

**定理1.3** 多面体 $g$ 满足 $1\notin a$ 当且仅当 $g\in\mathfrak{s}_1$。分类结果见表1。

定理1.3将在第2节中证明。

**定理1.4** 设 $g$ 是阶为 $p$ 的多面体,满足 $1\in a$,且 $a'_n$ 是 $\geq n$ 的整数的(有限)非空集合。则 $g$ 属于表2第一列所列的某一类型,对应的条件如第二列所述。

定理1.3和定理1.4共同完整地分类了所有多面体的类型。定理1.4将在第3、4、5、6节中证明,通过呈现中间结果来填充表2。

对于类型 $\{1,2\}$、$\{1,2,3\}$、$\{1,2,4\}$ 和 $\{1,2,\ell\}$($\ell\geq 6$ 为偶数),在第4节"图半径为1的多面体"和第5节"多面体类型分类的完成"中,我们将证明除有限个解外,其余所有解要么是锥体,要么属于 $\mathcal{w}_3$、$\mathcal{w}_4$、$b_\ell$、$b'_\ell$ 之一。

对于表2中其余的每个类型 $\{0,1\}$、$\{0,1,2\}$、$\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$,均存在该类型的广泛多面体类。对于类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的情况,文献[10]中已有所展示。例如,有以下显式类:所有围长(即最小面长度)为5的多面体均满足 $a=\{0,1\}$。除立方体外,所有包含四边形面的3-正则(即立方)多面体均满足 $a=\{0,1,2\}$[10, 定理1.2]。

本文将大大加强类型 $\{0,1\}$ 和 $\{0,1,2\}$ 的结果。在第3节中,我们将证明多面体满足 $a=\{0,1\}$ 当且仅当它不包含4-圈。在第4节中,我们将给出至少25个顶点的多面体满足 $a=\{0,1,2\}$ 的充要条件。

在第6节中,对于类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个,我们将构造相应类型的广泛多面体类。对于所有不出现在表1和表2中的非负整数集合 $a$,我们将在第5节中证明不存在满足 $a=a(g)$ 的多面体 $g$。

若一个图至少有 $k+1$ 个顶点,且无论移除其中少于 $k$ 个顶点,所得图仍连通,则称该图为 $k$-连通的。

若一个图可以嵌入到平面中且边仅在顶点处相交,则称该图为平面图的。平面图是平面图的及其一种平面嵌入。多面体图的嵌入在选定外部区域后是唯一的,因此我们默认将它们连同其嵌入一起考虑。

若一个平面图存在一种平面嵌入使得所有顶点都在某一个区域的边界上,则称该图为外平面图的。

对于(非平凡的)连通图 $g$,顶点 $u$ 的离心率 $\text{ecc}(u)$ 是 $u$ 到 $v\in v(g)$ 的最大距离。所有顶点中最大的离心率是 $g$ 的直径 $\text{diam}(g)$。等价地,$\text{diam}(g)$ 是 $g$ 中任意一对顶点之间的最大距离。$g$ 的半径 $\text{rad}(g)$ 是最小的顶点离心率。众所周知,对于任何连通图 $g$,$\text{rad}(g)\leq \text{diam}(g)\leq 2\text{rad}(g)$。

图的直径为1当且仅当它是完全图。图的半径为1当且仅当存在一个顶点与所有其他顶点相邻,也称为支配顶点。

给定平面图 $g$ 和 $u\in v(g)$,我们定义 $u$ 在 $g$ 中的平面邻域为 $g$ 的子图 $\gamma_u(g)$,其中 $e(\gamma_u(g))=\{e\in e(g): e \text{ 位于包含 } u \text{ 的某个区域上}\}$。

符号 $a'_n$ 各处表示 $\geq n$ 的整数的有限非空集合。

第2节完全用于证明定理1.3。接下来的四节用于证明定理1.4。在第3节中,我们将给出预备工作。在第4节中,我们将重点关注图半径为1的多面体这一重要类,这在后续工作中将是有用的。在第5节中,我们将完成表2中所述的多面体类型分类。在第6节中,我们将为表2中的若干类型构造广泛的多面体类。这些构造的代码见附录。用于证明定理1.4的结果将在第6节末尾进行总结。

---

## 章节节选

### $1\notin a$ 的多面体类型:定理1.3的证明

设 $1\nnotin a$。我们的第一个目标是证明 $g$ 要么是立方体,要么是球面的三角剖分(极大平面图)。反设 $g$ 包含一个面 $[u_1, u_2, \ldots, u_n]$,$n\geq 5$。

令 $u_{n+1}:=u_1$,$u_{n+2}:=u_2$。由于 $1\notin a$,则对于每个 $1\leq i\leq n$,顶点 $u_i$ 和 $u_{i+2}$ 有一个不同于 $u_{i+1}$ 的公共邻居。由平面性,唯一可能是存在 $v\in v(g)$ 与 $u_1, u_2, \ldots, u_n$ 中每一个都相邻。此外,对于每个 $1\leq i\leq n$,顶点 $u_i, u_{i+1}$ 有一个公共邻居 $w_i\neq v$。

接下来,对于每个 $1\leq i\leq n$,……

### $1\in a$ 情形的预备知识

本文余下部分的最终目标是证明定理1.4。在本节中,我们将建立一些关于一般图 $g$ 的 $a(g)$ 的辅助引理。

**引理3.1** 设 $g$ 是平面图。若存在 $a\geq 3$ 使得 $a\in a$,则 $2\in a$。

**证明** 设 $a\geq 3$ 使得 $a\in a$,并反设 $2\notin a$。我们声称 $g$ 包含一个同构于方锥体的子图。由假设,存在不同的 $u, v\in v(g)$ 使得 $n(u,v)\supseteq\{w_1, w_2, w_3\}$。由于 $2\notin a$,则 $w_1, w_2$ 有一个公共邻居 $x\notin\{u, v\}$,……

### 图半径为1的多面体

在本节及后续节中,我们将开始填充表2。我们需要一些关于图半径为1的多面体的辅助结果,这些结果在我们的论证中起着核心作用。

**引理4.1** 给定图半径为1的多面体 $g\not\simeq t_\ell$,$g$ 中恰有一个离心率为1的顶点。

**证明** 记图中离心率为1的顶点个数为 $i$。由定义,离心率为1的顶点与所有其他顶点相邻。若 $i\geq 4$,由平面性 $k_5$ 不是 $g$ 的子图,则 $i=4$ 且 $|v(g)|-$……

### 多面体类型分类的完成

本节的目的是证明表2第一列中 $1\in a$ 的多面体类型列表是完备的。为此,我们需要最后一个关键结果:分类所有满足 $0,3,4\notin a$ 且存在 $\ell\in a$($\ell\geq 5$)的多面体。

**命题5.1** 设 $g$ 是多面体图。$0,3,4\notin a$ 且 $\ell\in a$($\ell\geq 5$)当且仅当 $g\simeq b_\ell$ 或 $g\simeq b'_\ell$,其中 $\ell$ 为偶数。

**证明** 设 $\ell$ 是满足 $\ell\geq 5$ 且 $\ell\in a$ 的最小值,$x,y\in v(g)$ 使得 $|n(x,y)|=\ell$。设 $w_1, w_2, \ldots, w_\ell$ 为 $x, y$ 的公共邻居,……

### 广泛的解类

为了完成定理1.3的证明,我们还需为类型 $\{1,2,3\}\cup a'_4$、$\{1,2,4\}\cup a'_5$ 和 $\{0,1,2\}\cup a'_3$ 中的每一个构造无穷多个多面体,其中 $a'_n$ 是 $\geq n$ 的整数的有限非空集合。

**命题6.1** 对于任意(有限)非空整数集合 $a'_4$($\geq 4$),存在无穷多个多面体 $g$ 满足 $a(g)=\{1,2,3\}\cup a'_4$。

**证明** 毛毛虫树 $t$ 是一种树图,删除度为1的顶点后得到一条简单路径($t$ 的"中心路径")。毛毛虫树 $t$ 的度序列由……

## 致谢

riccardo w. maffucci 的部分工作得到"rita levi montalcini"青年研究者项目 pgr21dpcwz "数学及其应用中离散与概率方法"的支持,该项目授予 riccardo w. maffucci。作者感谢两位匿名审稿人提出的宝贵修改建议。

riccardo w. maffucci>
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号