直径为三的图是可识别的
《Discrete Applied Mathematics》:Graphs of diameter three are recognizable
【字体:
大
中
小
】
时间:2026年09月27日
来源:Discrete Applied Mathematics 1.1
编辑推荐:
# 直径为三的图族的可辨识性
## 摘要
图 $G$ 的删点子图(或称"卡牌")$G-v$ 是指从 $G$ 中删除顶点 $v$ 及所有与 $v$ 关联的边后所得到的无标记子图。$G$ 的所有卡牌的集合称为 $G$ 的"牌组"。若图 $H$ 与 $G$ 具有相同的牌组,则称
# 直径为三的图族的可辨识性
## 摘要
图 $G$ 的删点子图(或称"卡牌")$G-v$ 是指从 $G$ 中删除顶点 $v$ 及所有与 $v$ 关联的边后所得到的无标记子图。$G$ 的所有卡牌的集合称为 $G$ 的"牌组"。若图 $H$ 与 $G$ 具有相同的牌组,则称 $H$ 是 $G$ 的一个重构。若一个图与其所有重构同构,则称该图是可重构的。若图族 $\mathcal{F}$ 满足对每个 $G \in \mathcal{F}$,$G$ 的每个重构也属于 $\mathcal{F}$,则称该图族是可辨识的。本文证明了所有直径为三的图的族是可辨识的。
## 引言
本文考虑的所有图均为有限、简单、无向图。我们用 $V(G)$ 和 $E(G)$ 分别表示图 $G$ 的顶点集和边集。此处未定义的术语按文献[1]中的含义理解。图 $G$ 中顶点 $v$ 的度数记为 $\deg_G v$(或简记为 $\deg v$)。有限非递减序列 $[d_1, d_2, \ldots, d_n]$ 是图 $G$ 的度序列,记为 $DS(G)$,若 $G$ 的顶点可标记为 $v_1, v_2, \ldots, v_n$ 使得 $\deg_G v_i = d_i$。若 $G$ 有 $r_i$ 个度为 $d_i$ 的顶点($i = 1, 2, \ldots, k$),则度序列记为 $DS(G) = [(d_1)^{r_1}, (d_2)^{r_2}, \ldots, (d_k)^{r_k}]$。以 $u$ 为起点、$v$ 为终点的路径称为 $uv$-路径。若 $G$ 有 $uv$-路径,则从 $u$ 到 $v$ 的距离,记为 $d_G(u,v)$ 或简记为 $d(u,v)$,是 $uv$-路径的最短长度。图 $G$ 的直径,记为 $\mathrm{diam}(G)$,为 $\max_{u,v \in V(G)} d(u,v)$。$G$ 的连通度,记为 $\kappa(G)$,是使得 $G-S$ 不连通或 $G-S$ 仅含一个顶点的最小顶点集 $S$ 的大小。$v$ 的邻域,记为 $N_G(v)$ 或 $N(v)$,是与 $v$ 相邻的顶点集,我们用 $N[v]$ 表示集合 $N(v) \cup \{v\}$。对 $S \subseteq V(G)$,由 $S$ 诱导的 $G$ 的子图记为 $G[S]$。
图 $G$ 的删点子图(或卡牌)$G-v$ 是从 $G$ 中删除顶点 $v$ 及所有与 $v$ 关联的边后所得到的无标记子图。$G$ 的所有卡牌的集合称为 $G$ 的牌组,记为 $\mathcal{D}(G)$。设图 $G$ 和 $H$ 的顶点分别为 $v_1, v_2, \ldots, v_n$ 和 $w_1, w_2, \ldots, w_n$,若 $G - v_i \cong G - w_i$ 对所有 $1 \leq i \leq n$ 成立,则称 $G$ 和 $H$ 具有相同的牌组。若图 $H$ 与 $G$ 具有相同的牌组,则称 $H$ 是 $G$ 的一个重构。若一个图与其所有重构同构,则称该图是可重构的。若图族 $\mathcal{F}$ 满足对每个 $G \in \mathcal{F}$,$G$ 的每个重构也属于 $\mathcal{F}$,则称该图族是可辨识的;若对每个 $G \in \mathcal{F}$,$G$ 的所有属于 $\mathcal{F}$ 的重构都与 $G$ 同构,则称该图族是弱可重构的。若对任意 $G \in \mathcal{F}$,$G$ 是可重构的,则称图族 $\mathcal{F}$ 是可重构的(即 $\mathcal{F}$ 既是可辨识的又是弱可重构的)。定义在图上的参数 $p$ 是可重构的,若对任意图 $G$,$p$ 在 $G$ 的每个重构上取相同的值。
**重构猜想(RC)**[2]断言所有至少有三个顶点的图都是可重构的。由于至多十一个顶点的图已被证明是可重构的[3],本文仅考虑至少有十二个顶点的图。文献[4]、[5]、[6]、[7]对图的可重构性和重构猜想的研究提供了全面的综述。
1988年,杨永智[8]证明了:RC成立当且仅当每个2-连通图都是可重构的。Harary将RC推广到有向图如下:
**有向图重构猜想**[9]:任何至少有七个顶点的有向图 $D$ 都可以从其删点子有向图 $D - v_i$ 中重构出来。
有向图重构猜想被Stockmeyer[10]通过给出若干无穷反例族而否定。因此,若重构猜想被证明,则其证明将依赖于某些不能推广到有向图的图的特殊性质。其中一个这样的性质涉及补图中的距离。若 $\mathrm{diam}(G) > 3$,则 $\mathrm{diam}(\bar{G}) < 3$。此外,图 $G$ 是可重构的当且仅当 $\bar{G}$ 是可重构的。利用这两个结果,2003年,S. K. Gupta、Pankaj Mangal和Vineet Paliwal[11]证明了:RC成立当且仅当所有满足 $\mathrm{diam}(G) = 2$ 或 $\mathrm{diam}(G) = \mathrm{diam}(\bar{G}) = 3$ 的连通图 $G$ 都是可重构的。Ramachandran和Monikandan[12]将这一结果精细化,证明了:RC成立当且仅当所有满足 $\mathrm{diam}(G) = 2$ 或 $\mathrm{diam}(G) = \mathrm{diam}(\bar{G}) = 3$ 的2-连通图 $G$ 都是可重构的。进一步地,Devi Priya和Monikandan[13]给出了另一种化简,证明了:RC成立当且仅当所有满足 $\mathrm{diam}(G) = 2$ 或 $\mathrm{diam}(G) = \mathrm{diam}(\bar{G}) = 3$ 的2-连通非距离遗传图 $G$ 都是可重构的。
直径为一的图恰好是完全图,直径为二的图族被S. K. Gupta、Pankaj Mangal和Vineet Paliwal[11]证明是可辨识的。在他们的论文中,他们还证明了满足 $\mathrm{diam}(G) = \mathrm{diam}(\bar{G}) = 3$ 的图族是可辨识的。在本文中,我们证明所有直径为三的图的族是可辨识的。
## 各节概要
### $\ell$-河流图
阶数至少为三的图 $G$ 若存在一对不相邻的顶点 $m$ 和 $s$,使得 $G$ 中其他每个顶点都位于某条长度至多为 $\ell$ 的 $ms$-路径上,则称 $G$ 是 $\ell$-河流($\ell \geq 2$)。这样的 $m$、$s$ 分别称为山和海。注意 $\ell$-河流图是连通的。
为建立我们的主要结果——所有直径为三的图的族是可辨识的,我们按如下步骤进行:
**(i)** 在第3节中,我们将所有不含割点的3-河流图划分为五个互不相交的族。
**3-河流(无割点)($\mathcal{G}_1$)**
以下定理促使我们将所有不含割点的3-河流图划分为五个互不相交的图族。
**定理2** 若 $G$ 是直径至少为四的2-连通图,则 $G$ 的牌组中包含至少 $n-2$ 张直径至少为四的卡牌。
**证明** 由于 $G$ 是2-连通的,$G$ 的每张卡牌都是连通的。由于 $\mathrm{diam}(G) \geq 4$,存在两个不同顶点 $x, y \in G$ 使得 $d_G(x,y) \geq 4$。在卡牌 $G-z$ 中(其中 $z \in V(G) - \{x, y\}$),最短 $xy$-路径的长度至少为四。因此 $\mathrm{diam}(G-z) \geq 4$,对所有 $z \in V(G) - \{x, y\}$ 成立。
**3-河流(有割点)($\mathcal{G}_2$)**
接下来是族 $\mathcal{G}_2$ 的辨识。
**定理16** 满足 $\Delta(G) \leq n-2$ 的图 $G$ 属于族 $\mathcal{G}_2$ 当且仅当存在三张卡牌 $G-x$、$G-y$ 和 $G-z$ 使得:
(i) $G-x$ 是 $\mathcal{D}(G)$ 中唯一的非连通卡牌,$\deg(x) = n-2$,且 $G-x$ 包含一个孤立顶点;
(ii) $G-y$ 是 $\mathcal{D}(G)$ 中唯一的删端点卡牌,是连通的,且包含至少两个度为 $n-3$ 的不相邻顶点;
(iii) $G-z$ 是连通卡牌,$\deg_G z = n-3$,且 $G-z$ 包含一个度为 $n-2$ 的顶点和一个端顶点。
**证明** 充分性。计数定理
### 计数定理
两个3-河流图 $G_1$ 和 $G_2$ 称为根同构的,若存在一个同构 $\phi: G_1 \to G_2$ 使得 $\phi(\{m_1, s_1\}) = \{m_2, s_2\}$,其中 $\{m_1, s_1\}$ 和 $\{m_2, s_2\}$ 分别是 $G_1$ 和 $G_2$ 的山和海的集合。集合 $\{H_1^t(m,s), H_2^t(m,s), \ldots, H_k^t(m,s)\}$ 表示每个阶为 $t \geq 3$ 的根同构类3-河流图的一个代表元集合,其中每个图有一个指定的山 $m$ 和海 $s$。设 $\mathcal{K} = \mathcal{H}_1 \cup \mathcal{H}_3 \cup \mathcal{F}_1 \cup \mathcal{F}_2$。
**定义** 对图 $G$,令 $p(G, H_i^t(m,s))$ 表示……
## 结论
我们通过引入一些可能引导我们辨识所有图的直径的图族来结束本文。由定义可知,$\ell$-河流图的直径至多为 $\ell$。考虑所有 $\ell$-河流图($\ell \geq 5$)族的以下六个部分,记为 $\mathcal{J}$。
(i) 设 $\mathcal{J}_1 = \{G \in \mathcal{J}: \kappa(G) = 1\}$
(ii) 设 $\mathcal{J}_2 = \{G \in \mathcal{J}: \kappa(G) \geq 2, \mathrm{diam}(G) \leq \ell-1\}$
(iii) 设 $\mathcal{J}_3 = \{G \in \mathcal{J}: \kappa(G) \geq 2, \mathrm{diam}(G) > \ell-1$ 且对所有顶点 $v$,$\mathrm{diam}(G-v) \neq \ell\}$
(iv) 设 $\mathcal{J}_4 = \{G \in \mathcal{J}: \kappa(G) \geq 2, \mathrm{diam}(G) > \ell-1$ 且恰好对唯一一个顶点 $v$,$\mathrm{diam}(G-v) = \ell\}$
(v)
## 基金
本研究由印度政府原子能部国家高等数学委员会(NBHM),孟买通过一项主要研究项目资助。批准令编号:02011/14/2022/NBHM(R.P)/R&D II/10491。
## 利益冲突声明
作者声明不存在相关的财务或非财务利益冲突。
## 致谢
本研究由印度政府原子能部国家高等数学委员会(NBHM),孟买通过一项主要研究项目(编号:02011/14/2022/NBHM(R.P)/R&D II/10491)资助,批予第二作者。我们衷心感谢两位匿名审稿人逐行细致的审阅和宝贵建议,他们显著改进了定理的证明以及论文的整体风格和呈现方式。
J. Antony Aravind | S. Monikandan