不含P₅的无爪图的安全支配数

The Secure Domination Number of{P₅, K_1,3}-Free Graphs

摘要: 安全支配集是图论中重要的研究内容, 被广泛应用于网络安全, 资源优化配置等领域. 设集合S为 图G的一个支配集, 若对于V (G) − S中任意点u, 其在S中存在一邻点v, 使得(S − {v}) ∪ {u}是G的 支配集, J称S是G的一个安全支配集. 将G所有安全支配集中基数最小的安全支配集称作G的最小 安全支配集, 其基数称为G的安全支配数, 记作γ_s(G). 本文研究不含P5的无爪图的安全支配数上界 问题, 证明了独立数至少为3的不含P₅的无爪图G的安全支配数的上界为图G的独立数, 并且用例图 说明结论中的界是最佳的. 本文结果扩展了安全支配数的相关研究, 丰富了禁用子图条件下的安全 支配数界。

Abstract: Secure dominating set is an important topic in graph theory, which is widely applied in the network security, resource allocation and other areas. Let S be a dominating set of a graph G. If for any vertex u ∈ V (G)−S, there exists a neighbor v of u in S such that (S − {v}) ∪ {u} is also a dominating set of G, then S is said to be a secure dominating set of G. The cardinality of a minimum secure dominating set of G is defined as the secure domination number of G, denoted by γ_s(G). This paper investigates the upper bound problem of the secure domination number in {P₅, K_1,3}-free graphs. It is proved that if G is a {P₅, K_1,3}-free graph with independence number at least 3, then the upper bound of secure domination number is the independence number of G; a figure is given to show that the bound in the conclusion is best possible. This result extends relevant research on the secure domination number and enriches its bounds under forbidden subgraph conditions.