Connected domination versus dominating sets inducing large components

Teresa W. Haynes

doi:10.1016/j.disc.2025.114884

2025-11-01

PRE

Teresa W. Haynes *

Michael A. Henning

DOI：10.1016/j.disc.2025.114884

原文链接

原文求助

摘要

En 中文

图G中的一个支配集D是G的顶点集V(G)的一个子集，使得V(G) \ D中的每个顶点在D中都有一个邻居，其中两个顶点若相邻则互为邻居。此外，如果由D导出的子图G[D]是连通图，则D是G的一个连通支配集。图G的连通支配数，记作gamma(c)(G)，是G的所有连通支配集中基数的最小值。对于整数k ≥ 1，k-分量支配数gamma(k)(G)（由Alvarado et al. (2016) [2]首次定义），是G的所有支配集D中基数的最小值，其中G[D]的每个分量阶数至少为k。我们注意到，k-分量支配是支配和全支配的自然推广，因为gamma(1)(G) = gamma(G)且gamma(2)(G) = gamma(t)(G)，其中gamma(G)是图G的支配数，gamma t(G)是图G的全支配数。我们证明，对于k ≥ 1，若G是一个阶数至少为k的连通图，则gamma(c)(G) ≤ (k+2/k) gamma(k)(G) - 2，且对于所有k ≥ 1，这个界是紧的。该界推广了Duchet和Meyniel在1982年的一个结果（当k=1时）以及Favaron和Kratsch在1991年的一个结果（当k=2时）。我们（k+2）刻画了满足gamma(c)(T) = (k+2/k) gamma(k)(T) - 2的阶数至少为k的树T。(c) 2025 Elsevier B.V. 版权所有，包括文本和数据分析、AI训练及类似技术的使用权。

Keyword:

Connected domination

k-component domination

Total domination

Domination