关于由k-正则图构造的(k+1)-正则图的全控制集与原图控制集大小关系的验证问题

嗨，咱们来一步步拆解这个图论问题，先把核心概念和已知结论理清楚，再聚焦到你提出的猜想上：

先明确核心定义 #

• 全控制集（Total Dominating Set）：对于图$G$，顶点集$S$是全控制集的充要条件是：$G$中每一个顶点（包括$S$里的顶点）都在$S$中有至少一个邻居。我们用$\gamma_t(G)$表示$G$的最小全控制集的大小。
• 控制集（Dominating Set）：对于图$G$，顶点集$D$是控制集的充要条件是：$G$中所有不在$D$里的顶点，都在$D$中有至少一个邻居。我们用$\gamma(G)$表示$G$的最小控制集的大小。

很明显，对任意图$G$都有$\gamma_t(G) \geq \gamma(G)$——毕竟全控制集的约束更强，它要覆盖所有顶点，而控制集只需要覆盖不在自身集合内的顶点。

图$G'$的构造方式 #

给定一个无三角形的$k$-正则图$G$（题目特意提到：无三角形这个条件在本次问题里不重要），我们构造出一个无三角形的$(k+1)$-正则图$G'$：

1. 取$G$的两个完全相同的副本，把左边副本的顶点记为$u_1, u_2, ..., u_n$，右边副本的顶点记为$v_1, v_2, ..., v_n$；
2. 给每一组对应顶点$u_i$和$v_i$之间添加一条边——这样每个顶点的度数就从$k$变成了$k+1$，满足$(k+1)$-正则的要求。

你的猜想与已证的半边结论 #

你提出的猜想是：$\boldsymbol{\gamma_t(G') = 2 \times \gamma(G)}$

首先，我们已经能轻松证明$\boldsymbol{\gamma_t(G') \leq 2 \times \gamma(G)}$，这个逻辑很直观：
假设$D = {u_1, u_2, ..., u_{|D|}}$是左边$G$副本的一个最小控制集，那么我们取集合$S = {u_1, ..., u_{|D|}, v_1, ..., v_{|D|}}$，这个集合就是$G'$的一个全控制集：

• 对于左边副本的任意顶点：如果它在$D$里，那么它的对应顶点$v_i$在$S$中，且$u_i$和$v_i$有边相连，满足全控制的要求；如果它不在$D$里，那么它在$D$中存在邻居，这个邻居也在$S$里，同样满足要求。
• 右边副本的顶点情况完全对称，要么自身在$S$中对应左边的邻居，要么不在$S$时在右边的$D$副本里有邻居。

现在剩下的关键就是要证明$\boldsymbol{\gamma_t(G') \geq 2 \times \gamma(G)}$——也就是要说明$G'$的最小全控制集的大小，至少是原图$G$最小控制集大小的两倍。这部分需要进一步的推导哦。

备注：内容来源于stack exchange，提问作者Ankit Gayen