无三角形图的重支配数（hop domination number）的上界

《Discrete Applied Mathematics》：Tight upper bounds on the hop domination number of triangle-free graphs

　　摘要
对于一个图 ??，如果 ???(??) 的一个子集 ?? 是 ?? 的一个跳支配集（即图中每个不在 ?? 中的顶点都可以在 ?? 中找到一个距离为 2 的邻居），那么这个子集 ?? 就被称为 ?? 的一个跳支配集。图 ?? 的跳支配数记为 ????(??)，它是 ?? 的一个跳支配集的最小基数。在本文中，我们证明了对于一个具有至少 15 个顶点的无三角形连通图 ??，如果 ???(??)≥2，则 ????(??)≤2????，并且这个界限是紧的。我们还给出了包含哈密顿路径或哈密顿循环的无三角形图 ?? 的 ????(??) 的一些紧上界。

引言
设 ?? 是一个图。如果 ???(??) 的一个子集 ?? 满足 ???(??)??? 中的每个顶点在 ?? 中都有邻居，那么这个子集 ?? 就是 ?? 的一个支配集。图 ?? 的支配数记为 ???(??)，它是 ?? 的一个支配集的最小基数。如果 ???(??) 的一个子集 ?? 满足 ???(??) 中的每个顶点在 ?? 中都有邻居，并且每个顶点都是唯一的邻居，那么这个子集 ?? 就是 ?? 的一个完全支配集。图 ?? 的完全支配数记为 ?????(??)，它是 ?? 的一个完全支配集的最小基数。图论中的支配集问题一直是许多研究者关注的课题，它与网络覆盖和控制问题相关，并应用于通信网络、社交网络等多个领域（参见 [2]、[3]、[4]、[5]）。
对于一个图 ??，如果对于任何属于 ???(??)??? 的顶点 ??，都存在一个属于 ?? 的顶点 ???? 使得在图 ?? 中 ???? 和 ?? 之间的距离恰好为 2，那么 ?? 就是 ?? 的一个跳支配集。图 ?? 的跳支配数记为 ????(??)，它是 ?? 的一个跳支配集的最小基数。根据定义，对于完全图 ????，有 ????(????)=??。跳支配集的概念最初由 Natarajan 和 Ayyaswamy 在 [12] 中提出。Henning 和 Rad [9] 进一步探讨了这个概念：他们证明了如果一个具有 n 个顶点的连通图 ??（n≥3）满足 ????(??)=n?1 当且仅当 ??????n（即从 ???? 中删除一条边后得到的图），从而回答了 Natarajan 和 Ayyaswamy 在 [12] 中提出的问题；此外，他们还为图的跳支配数给出了概率上界，并且还证明了对于平面二分图和平面弦图，跳支配集的判断问题是 NP 完全的。Henning、Pal 和 Pradhan [8] 也给出了更多的计算结果。此外，他们还发现了无三角形图的跳支配数和完全支配数之间的一个重要关系：

定理 1.1
如果 ?? 是一个无三角形图，那么 ????(??)≤?????(??)。

考虑到一个完全的 ? 部分图 ????，…，??，其中每个部分的大小为 ??（?≥3），我们可以看到 ????(??)??????(??) 的差可以任意大，这意味着对于一般的图 ??，????(??)≤?????(??) 并不一定成立。他们进一步证明了，如果 ?? 是一个具有至少 15 个顶点的无三角形图，并且 ???(??)≥2，那么 ????(??)≤(1+ln????(??)???(??))?。正如 Henning 和 Rad [9] 的上述结果所示，图 ?? 中的一个大团会增加图 ?? 的跳支配数。因此，为了获得 ????(??) 的一个好的上界，我们需要对图 ?? 施加一些禁止子图的条件，例如无三角形性。

受此观察以及他们关于无三角形图跳支配数的结果启发，在本文中，我们专注于给出无三角形图 ?? 的 ????(??) 的一个紧上界。我们的主要结果如下：
定理 1.2
设 ?={???,???,???,????,???,????,??′??}，其中图 ???、???? 和 ??′?? 在图 1 中给出。设 ?? 是一个正整数且 ??≥4。对于一个具有 n 个顶点的无三角形连通图 ??，如果 ???(??)≥2 并且 ????，那么 ????(??)≤2????。

定理 1.2 表明，对于一个具有 ???(??)≥2 的无三角形图 ??，如果 ?? 至少有 15 个顶点，那么 ????(??)≤2????。
设 ????:??????…???? 是一个包含 ?? 个顶点的路径，并且对于 ???? 中的每个顶点 ????，我们在 ???? 和 ???? 之间连接一条边，然后在顶点 ???? 处连接一个 4-环。设 ?? 是得到的图。图 2 展示了当 ??=6 时的情况。对于这个图 ??，我们总是有 ???(??)≥2 并且 ????(??)=2?|???(??)|?。因此，定理 1.2 中的 2? 倍比率是紧的。
我们还展示了如果无三角形图包含一个哈密顿路径或哈密顿循环，这个比率可以提高到大约 1?（见推论 2.4）。

Henning [7] 证明了每个没有孤立顶点的图 ?? 都满足不等式 ???(??)≤?????(??)≤2????(??)。因此，根据定理 1.1，对于无三角形连通图 ??，有 ????(??)≤?????(??)≤2????(??)。考虑到这种关系，当比较这三个图参数的紧上界时，对于具有 ???(??)≥2 的连通无三角形图 ??，可以获得什么样的相对大小关系呢？
在 [11] 中，McCuaig 和 Shepherd 展示了以下内容：
定理 1.3
对于一个具有 n 个顶点的连通图 ??，如果 ???(??)≥2 并且 ?? 不是图 3 中的图，那么 ???(??)≤2????。

注 1.4
注意对于图 3 中的图 ????，有 ???(????)≤2???+2?。因此，结合定理 1.3，我们可以得出对于每个具有 ???(??)≥2 的连通图 ??，有 ???(??)≤2???+2?。
如 [11] 中所示，存在无限多个具有 ???(??)=2?|???(??)|? 和 ???(??)≥2 的连通无三角形图 ??。
另一方面，Henning 和 Yeo [10] 给出了图 ?? 的 ?????(??) 的一个紧上界 |???(??)|/2+max?{1,|???(??)|2(??+1)，其中图 ?? 的周长至少为 ??，这意味着对于连通无三角形图 ??，我们有紧上界 3?|???(??)|?。
因此，有些令人惊讶的是，从我们的主要定理中可以观察到，对于具有 ???(??)≥2 的连通无三角形图 ??，????(??) 的紧上界不仅接近，实际上与它完全相等。
有人可能会问，如果我们在研究中放宽最小度条件“???(??)≥2”对于较大的无三角形图会发生什么。为了回答这个问题，我们给出了一些初步结果。
对于一个图 ??，设 ??????????(??:2) 是一个图，其顶点集为 ???(??)，并且当且仅当两个顶点在图 ?? 中的距离恰好为 2 时，它们在 ??????????(??:2) 中是相邻的。对于图 ?? 中的一个顶点 ??，设 ???(??;??) 是 ?? 在图 ?? 中的 2-步邻居集合，即 ???(??;??)?{??∈???(??)?{??}:????????(??) 且 ?????(??)∩?????(??)≠0?}。以下是一些关于 ????(??) 的基本观察结果，某些结果参考了 [9]：
命题 1.5
设 ?? 是一个连通图，并且 ???=??????????(??:2)。以下结论成立：
(i) ????(??)=???(???)；
(ii) 对于每个顶点 ??，都有 ???(??;??)=?????(??)。
Ore [13] 证明了，对于任何具有 n 个顶点的图 ??，如果 ???(??)≥1，那么它满足 ???(??)≤n/2。注意，任何具有至少 4 个顶点的连通无三角形图 ?? 都满足 ???(???)≥1，除非 ??????,??，其中 ??≥3。由于 ????(???,??)=2，结合这些事实以及命题 1.5(i)，我们可以得出以下定理：
定理 1.6
设 ?? 是一个正整数且 ??≥4。如果 ?? 是一个具有 n 个顶点的连通无三角形图，那么 ????(??)≤n2。
这个定理中对 ????(??) 的限制是最优的。为了看到这一点，考虑从 ???,?? 通过将每条边分割成三个顶点得到的图 ??。我们看到 ????(??)=2?|???(??)|?1?，从而表明定理 1.6 中 ????(??) 上界的 12 倍比率是紧的。由于 ?? 可以任意大，我们的主要结果定理 1.2 显著细化了定理 1.6 中 ????(??) 上界的系数，将其从 12 降低到 2?，适用于具有 ???(??)≥2 的连通无三角形图。

小节片段：哈密顿无三角形图
在本小节中，我们提出了一些关于图 ?? 的哈密顿性的观察结果。我们给出了包含哈密顿路径或哈密顿循环的无三角形图 ?? 的 ????(??) 的紧上界。

命题 2.1
设 ?? 是一个无三角形图。那么以下结论成立：
(i) 如果对于 ?? 中的某个两个顶点 ?? 和 ??′，有 0?≠?????(??′)=?????(??)，那么 ????(??)≤????(?????)；
(ii) 对于图 ?? 的一个生成子图 ??，有 ????(??)≤????(??)。

证明
(i) 取 ????? 的一个最小跳支配集 ??。如果 ??′∈??，那么 ??′ 是 ?? 的 2-步邻居。如果 ??′???，那么 ??′ 有一个 2-步邻居 ??。

一个未解决的问题
考虑给出具有较大周长的图的跳支配数的紧上界是一个自然的扩展。因此，我们提出以下未解决的问题：
问题 1
设 ?? 是一个正整数且 ??≥4。确定一个最小值 ???(??,??)，使得以下命题成立：如果 ?? 是一个具有足够大的 ?? 个顶点的连通图，并且 ???(??)≥2 且周长至少为 ??，那么 ????(??)≤???(??,??)。
考虑到一个大的奇数循环，我们看到 ???(??,??)≥???/3?。在本文中，我们证明了 ???(??,4)=mfrac

致谢
作者衷心感谢审稿人的宝贵评论和建议，特别是提供了显著改进手稿的简洁证明。Fujita Shinya 受到了日本学术振兴会（JSPS KAKENHI）基金（编号 JP23K03202）的支持。Boram Park 受到了韩国国家研究基金会（NRF）（由韩国政府资助，MSIT）的资助（编号 RS-2025-00523206），并且得到了首尔国立大学的新教师创业基金的支持。